0

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

它对于较低的数字运行良好，但随着您的增加，时间也会增加 - 呈指数增长。所以像 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;
}
}
4

4 回答 4

5

有更好的求素数算法，但作为一种快速解决方法，您只需要通过当前数的平方根向上测试因子，因为如果您找到高于平方根的因子，那么您应该找到低于平方根的因子平方根。

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

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

如果需要更高的效率，您可以实施埃拉托色尼筛法，以便您只检查本身是质数的可能因素。

于 2013-03-18T23:46:11.493 回答
1

每次找到一个质数时，您确实应该存储一组质数，这样您就可以避免每次都除以所有数字。

这件事：currentNum % 2 != 0可以写成currentNum & 1.

你的算法也是错误的，试着给 3 作为输入。

于 2013-03-18T23:50:35.287 回答
1

使用 Eratosthenes Sievie：http ://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 您将在 O(n log n log n) 中找到低于给定数字的所有素数，并且您需要遍历整个表。

于 2013-03-18T23:57:28.247 回答
0

我写了一个。我不能确保一切都是正确的。我已经在我的机器上测试了 1000000，它只用了 31 毫秒。内存要求：1000000*1bytes=1mb

public class FindPrime {

/**
 * @param args
 */
public static void main(String[] args) {
    long begin=System.currentTimeMillis();
    System.out.println(findPrime(1000000));

    System.out.println("cost time="+(System.currentTimeMillis()-begin)+"ms");

}

public static long findPrime(int max){
    boolean data[]=new boolean[max+1];
    long sum=0;
    int stop=(int) Math.sqrt(max);
    for(int i=2;i<=stop;i++){
        if(data[i]==false){
            sum+=i;

            int index=i+i;
            while(index<=max){
                data[index]=true;
                index=index+i;
            }
            //System.out.println(i);
        }
    }

    stop=stop+1;

    for(;stop<=max;stop++){
        if(data[stop]==false){
            sum+=stop;
            //System.out.println(stop);
        }
    }

    return sum;
}

}

于 2013-03-19T02:19:42.343 回答