Java中的Euler #3项目

Question

Euler #3项目：

13195的素因子为5、7、13和29。数字600851475143中最大的素因子是什么？

这是我的解决方案：

public class PrimeFactorFinder {
    
    private static final long NUMBER = 600851475143L;

    public static void main(String[] args) {
        long time = System.nanoTime();
        long result = 0;
        for(int i = 2; i < NUMBER; i++) {
            if(NUMBER % i == 0 && isPrime(NUMBER / i)) {
                result = NUMBER / i;
                break;
            }
        }
        System.out.println("Result: " + result + "\nTime required to calculate in nanoseconds: " + (System.nanoTime() - time));
    }

    private static boolean isPrime(long l) {
        for(long num = 2, max = l / 2 ; num < max; num++) {
            if(l % num == 0) {
                return false;
            }
        }
        return true;
    }
    
}

输出：

结果:以纳秒计算所需的6857 时间: 1154999669

问题：

• 我对isPrime()方法特别恼火。有更好的方法吗？多么?
• 有什么一般性意见吗？

Answer 1

我对您的程序进行了调整，使其更快、更正确(用于任意的大型测试用例)。我改变了一些事情：

1. 您的计数器i应该是long类型的。如果您将测试用例更改为600851475149L (素数)，您将看到i会在某个点将负数括起来。
2. 如果NUMBER是素数，您应该在1开始主循环。
3. 您的主循环只需要转到Math.sqrt(NUMBER)。这是保持运行时受限的关键。否则，在某些测试用例中，您可能会循环到一个非常大的数目。
4. 第3点的一部分是，一旦找到除数i，除了检查NUMBER/i是否为素数(就像您已经做的那样)，您还应该检查i是否为素数。
5. 您可以跳过偶数在您的主循环，如果您确保数字是奇数除以所有的因素2最初。
6. isPrime()循环可以从3开始，然后跳过2。

下面是最后修改的代码：

public class PrimeFactorFinder {
    private static long NUMBER = 600851475143L;

    public static void main(String[] args) {
        long time   = System.nanoTime();
        long result = 1;

        // If NUMBER is even, get rid of all factors of 2.
        while ((NUMBER & 1) == 0) {
            NUMBER /= 2;
            result = 2;
        }
        // We only need to iterate to sqrt of the number.
        long end = (long) Math.sqrt(NUMBER);
        for (long i = 1; i < end; i += 2) {
            if (NUMBER % i == 0) {
                if (isPrime(NUMBER / i)) {
                    // This must be the largest prime.
                    result = NUMBER / i;
                    break;
                } else if (isPrime(i)) {
                    // This is a prime factor, but possibly not the largest.
                    // Record it as the largest prime factor so far.
                    result = i;
                }
            }
        }
        System.out.println("Result: " + result +
                "\nTime required to calculate in nanoseconds: " +
                (System.nanoTime() - time));
    }

    private static boolean isPrime(long l) {
        long max = (long) Math.sqrt(l);
        for(long num = 3; num < max; num+=2) {
            if(l % num == 0) {
                return false;
            }
        }
        return true;
    }
}

输出：

结果:6857堆栈--以纳秒为单位计算所需的新线时间: 774264336修改: 结果:6857 所需的纳秒时间: 6942153

Answer 2

将很快修改之前的代码。就目前而言，最优的原始性检查。

    private static boolean isPrime(long l) {
        // Each prime number can be expressed as 6x+1 or 6x-1 except 2 and 3. Eliminate them.
        if(l<4){
            return true;
        }
        if(l%2==0 || l%3==0){
            return false;
        }
        // Best way to shorten the search is to navigate upto the sqrt of the number.
        long sqrt = (long)Math.sqrt(l);
        // That's right. We are incrementing the loop by 6 with 2 and 3 eliminated.
        for(long num = 6 ; num<=sqrt; num+=6) {
            if(l % (num-1) == 0 || (l%(num+1)==0)) { //Possible primes: 6x+1 and 6x-1 
                return false;
            }
        }
        return true;
    }

Answer 3

下面是我的努力，它解决了在i7 iMac上使用大约240 effort的问题：

private long highest;

// checks if `f` is a factor of `n`,
// returning divided `n` accordingly
private long factorize(long n, long f) {
    if (n < f) return n;
    while (n % f == 0) {
        n /= f;
        if (f > highest) {
            highest = f;
        }
    }
    return n;
}

public long find(long n) {
    highest = 1;

    // check the two simplest cases
    n = factorize(n, 2);
    n = factorize(n, 3);

    // and then all numbers in the form 6x - 1 and 6x + 1
    if (n >= 5) {
        for (long i = 5; i * i <= n; i += 6) {
            n = factorize(n, i);
            n = factorize(n, i + 2);
        }
    }
    return (n == 1) ? highest : n;
}

这是@thepace算法的修正版本，对2，3，然后6n -1和6n +1进行了特例测试