Project Euler #3 takes forever in Java

java, prime-factoring, primes

Solution

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();
}

Problem

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; } } ```

Original source