Project 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

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

如果您想为一个数快速生成不同的素数因子，请使用此方法，该方法可以在每次迭代时使该数变小。您可以将int更改为long，它应该适合您。

Answer 2

您应该在找到每个因子时将其划分出来。然后无需测试它们的质数，当我们按升序枚举可能的除数时（任何这样找到的除数都不能是复合的，它的因子已经被划分出来了）。然后您的代码变成：

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

虽然不是用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();
}