Project Euler #3 takes forever in Java

Question

Problem #3 on Project Euler is:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143?

My solution takes forever. I think I got the right implementation; however, when testing with the big number, I have not being able to see the results. It runs forever. I wonder if there's something wrong with my algorithm:

public class LargestPrimeFactor3 {

    public static void main(String[] args) {
        long start, end, totalTime;
        long num = 600851475143L;
        long pFactor = 0;

        start = System.currentTimeMillis();

        for(int i = 2; i < num; i++) {
            if(isPrime(i)) {                
                if(num % i == 0) {
                    pFactor = i;                        
                }
            }
        }

        end = System.currentTimeMillis();
        totalTime = end - start;
        System.out.println(pFactor + " Time: "+totalTime);
    }

    static boolean isPrime(long n) {

        for(int i = 2; i < n; i++) {
            if(n % i == 0) {
                return false;
            }
        }        
        return true;
    }     
}

Answer 1

Although not in Java, I think you can probably make out the following. Basically, cutting down on the iterations by only testing odd divisors and up to the square root of a number is needed. Here is a brute force approach that gives an instant result in C#.

static bool OddIsPrime (long oddvalue)  // test an odd >= 3 
{
    // Only test odd divisors.
    for (long i = 3; i <= Math.Sqrt(oddvalue); i += 2)
    {
        if (value % i == 0)
            return false;
    }
    return true;
}

static void Main(string[] args)
{
    long max = 600851475143;   // an odd value
    long maxFactor = 0;

    // Only test odd divisors of MAX. Limit search to Square Root of MAX.
    for (long i = 3; i <= Math.Sqrt(max); i += 2)
    {
        if (max % i == 0)
        {
            if (OddIsPrime(i))  // i is odd
            {
                maxFactor = i;
            }
        }
    }
    Console.WriteLine(maxFactor.ToString());
    Console.ReadLine();
}

Answer 2

You should divide out each factor as it is found. Then there is no need to test them for primality, when we enumerate the possible divisors in ascending order (any thus found divisor can't be compound, its factors will be divided out already). Your code then becomes:

class LargestPrimeFactor4 {

    public static void main(String[] args) {
        long start, end, totalTime;
        long num = 600851475143L;   // odd value is not divided by any even
        long pFactor = 1L;

        start = System.currentTimeMillis();

        for(long i = 3L; i <= num / i; ) 
        {
            if( num % i == 0 ) {
                pFactor = i;
                num = num / i;
            }
            else {
                i += 2;
            }
        }
        if( pFactor < num ) { pFactor = num; }

        end = System.currentTimeMillis();
        totalTime = end - start;
        System.out.println( pFactor + " Time: " + totalTime);
    }
}

Answer 3

public HashSet<Integer> distinctPrimeFactors(int n) //insane fast prime factor generator
{
    HashSet<Integer> factors = new HashSet<Integer>();
    int lastres = n;
    if (n==1)
    {
        factors.add(1);
        return factors;
    }
    while (true)
    {
        if (lastres==1)
            break;
        int c = 2;
        while (true)
        {
            if (lastres%c==0)
                break;
            c++;
        }
        factors.add(c);
        lastres/=c;
    }
    return factors;
}

If you want to generate distinct prime factors for a number quickly use this method which makes the number smaller on each iteration. You can change int to long and it should work for you.

Answer 4

Here's pseudocode for integer factorization by trial division:

define factors(n)

    z = 2

    while (z * z <= n)

        if (n % z == 0)
            output z
            n /= z

        else
            z++

    output n

The easiest way to understand this is by an example. Consider the factorization of n = 13195. Initially z = 2, but dividing 13195 by 2 leaves a remainder of 1, so the else clause sets z = 3 and we loop. Now n is not divisible by 3, or by 4, but when z = 5 the remainder when dividing 13195 by 5 is zero, so output 5 and divide 13195 by 5 so n = 2639 and z = 5 is unchanged. Now the new n = 2639 is not divisible by 5 or 6, but is divisible by 7, so output 7 and set n = 2639 / 7 = 377. Now we continue with z = 7, and that leaves a remainder, as does division by 8, and 9, and 10, and 11, and 12, but 377 / 13 = 29 with no remainder, so output 13 and set n = 29. At this point z = 13, and z * z = 169, which is larger than 29, so 29 is prime and is the final factor of 13195, so output 29. The complete factorization is 5 * 7 * 13 * 29 = 13195.

There are better algorithms for factoring integers using trial division, and even more powerful algorithms for factoring integers that use techniques other than trial division, but the algorithm shown above will get you started, and is sufficient for Project Euler #3. When you're ready for more, look here.

Answer 5

Two things to improve performance:

static boolean isPrime(long n)
{
    for(int i = 2; i <= sqrt(n); i++)  // if n = a * b, then either a or b must be <= sqrt(n).
    {
        if(n % i == 0)
        {
            return false;
        }
    }        
    return true;
}  

now for the main loop

for(int i = num; i > 1; i--) // your interested in the biggest, so search from high to low until you have a match
{
    if(num % i == 0 && isPrime(i)) // check for num % i == 0 is faster, so do this first
    {
        pFactor = i;
        break; // break if you have a factor, since you've searched from the top
    }
}

There are still things one can improve here, but that's for you to find out. Think of modifying num. Have fun with project Euler :)

Answer 6

You could just prime factorize the number and then the largest prime factor would be the answer:

import java.util.ArrayList;
import java.util.Collections;

public class PrimeFactorization {

    /* returns true if parameter n is a prime number, 
         false if composite or neither */
    public static boolean isPrime(long n) {
        if (n < 2) return false;
        else if (n == 2) return true;
        for (int i = 2; i < Math.pow(n, 0.5) + 1; i++)
            if (n % i == 0)
                return false;
        return true;
    }

    /* returns smallest factor of parameter n */
    public static long findSmallestFactor(long n) {
        int factor = 2; // start at lowest possible factor
        while (n % factor != 0) { // go until factor is a factor
            factor++; // test the next factor
        }
        return factor;
    }

    /* reduces the parameter n into a product of only prime numbers
       and returns a list of those prime number factors */
    public static ArrayList<Long> primeFactorization(long n) {

        ArrayList<Long> primes = new ArrayList<Long>();
          // list of prime factors in the prime factorization
        long largestFactor = n / findSmallestFactor(n);    

        long i = 2;
        while (i <= largestFactor) { 
          // for all possible prime factors 
          // (2 - largest factor of the number being reduced)

            if (isPrime(i) && n % i == 0) { 
                // if this value is prime and the number is divisible by it

                primes.add(i); // add that prime factor to the list
                n /= i; // divide out that prime factor from the number 
                        // to start reducing the new number
                largestFactor /= i; // divide out that prime factor 
                       // from the largest factor to get the largest 
                       // factor of the new number
                i = 2; // reset the prime factor test
            } else {
                i++; // increment the factor test
            }
        }

        primes.add(n); // add the last prime number that could not be factored
        Collections.sort(primes);
        return primes;
    }
}

And then call it like this:

ArrayList<Long> primes = PrimeFactorization.primeFactorization(600851475143L);
System.out.println(primes.get(primes.size() - 1));

The entire thing takes only a few milliseconds.

Answer 7

It's not the perfect solution, but it will work for 600851475143.

public static void main(String[] args) {
    long number= 600851475143L;
    int rootOfNumber = (int)Math.sqrt(number)+10;
    for(int i = rootOfNumber; i > 2; i--) {
        if(number % i == 0) {
            if(psudoprime(i)) {
                System.out.println(i);
                break;
            }
        }
    }

}

public static boolean psudoprime(int num) {
    for(int i = 2; i < 100; i++) {
        if(num % i == 0) {
            return false;
        }
    }
    return true;
}

Answer 8

public class LargestPrimeFactor {
    static boolean isPrime(long n){
        for(long i=2;i<=n/2;i++){
            if(n%i==0){
                return false;                                               
            }
        }
        return true;    
    }

    static long LargestPrimeFact(long n){
        long largestPrime=0;
        for(long i=2;i<Math.sqrt(n)/2;i++){
            if(n%i==0){
                if(isPrime(i)){
                    largestPrime=i;
                }
                }                                       
            }
        return largestPrime;
    }
    public static void main(String args[]) {
        System.out.println (LargestPrimeFact(600851475143L));
    }
}

Source: http://crispylogs.com/project-euler-problem-3-solution/

Answer 9

This one works perfectly!!

public class Puzzle3 {
public static void main(String ar[])
{
    Long i=new Long("1");
    Long p=new Long("600851475143");
    Long f=new Long("1");
    while(p>=i)
    {
        if(p%i==0)
        {
            f=i;
            p=p/i;
            int x=1;
            i=(long)x;
        }
        i=i+2;
    }
    System.out.println(f);
}

}