项目Euler＃3用Java取胜

Question

欧拉计画的问题3是：

13195的主要因子是5、7、13和29。

600851475143的最大素数是多少？

我的解决方案需要永远。我认为我得到了正确的实施；但是，在进行大量测试时，我无法看到结果。它永远运行。我想知道我的算法是否有问题：

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

尽管不是Java语言，但我认为您可以做到以下几点。基本上，只需要测试奇数除数就可以减少迭代次数，并且最多可以减少数字的平方根。这是一种蛮力方法，可在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();
}