java - 更有效的方法？

Question

这个问题不太可能对任何 future 的访客有帮助；它只与一个较小的地理区域、一个特定的时间点或一个非常狭窄的情况相关，通常不适用于全世界的互联网受众。如需帮助使此问题更广泛适用， visit the help center 。

已关闭 10 年前。

我想知道是否有更有效的方法来运行这个程序？

对于较低的数字，它运行良好，但随着数字的增加，时间也会呈指数增长。所以像 1000000 这样的数字需要很长时间

import java.util.*;

public class SumOfPrimes {

public static void main(String args[]) {
    Scanner in = new Scanner(System.in);
    long number = 0;

    System.out.println("This program outputs the sum of the primes of a given number.");
    System.out.print("Please enter a number: ");
    number = in.nextLong();

    System.out.println("The sum of the primes below "+number+" is: "+sumOfPrimes(number));
}

public static long sumOfPrimes(long n){
    long currentNum = 2;
    long sum = 0;
    if (n > 2){
        sum = sum + 2;
    }

    while (currentNum <= n) {
        if (currentNum % 2 != 0 && isPrime(currentNum)) {
            sum = sum + currentNum;
        }
        currentNum++;
    }
return sum;
}

public static boolean isPrime(long currentNum){
    boolean primeNumber = true;

    for (long test = 2; test < currentNum; test++) {
        if ((currentNum % test) == 0){
            primeNumber = false;
        }
    }

return primeNumber;
}
}

Answer 1

有更好的素数查找算法，但作为一个快速解决方案，您只需要测试当前数字的平方根以上的因子，因为如果您找到高于平方根的因子，那么您应该找到了低于平方根的因子。

long stop = (long) Math.sqrt(currentNum);
for (long test = 2; test <= stop ; test++) {

此外，如果您找到了一个因子并证明了数字的合数，则跳出循环并返回false。

如果需要更高的效率，您可以实现 Sieve of Eratosthenes这样您就只检查可能的素数因子。