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

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 2

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 3

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 :)