求两个以下所有质数的总和 million.My 程序不适用于非常大的数

Question

这是我用于计算 primes.It 之和的代码，它适用于一些较小的数字，但如果它是 2000000（200 万），它永远不会 ends.Anybody 可以帮助我？

import java.math.BigInteger;
public class Problem010{
    public static void main(String[] args) {

        BigInteger sum = new BigInteger("2");

        //for (int i=3; i<2000000; i++) {
        for(int i=3; i<10; i++){
            for (int j=2; j<i; j++){
                if (i % j == 0) 
                    break;
                else if (i == j+1){
                    sum = sum.add(BigInteger.valueOf(i));
                }
            }
        }
        System.out.println("Sum  = "+sum); 
    }
}

Answer 1

你的答案是 142913828922，但如何回答？

我只是稍微改变了你的算法：

public static void main(String[] args) {

    BigInteger sum = new BigInteger("2");
    boolean isPrime = true;
    for (int i=3; i<2000000; i++) {
    double aa = Math.sqrt((double)i);
        for (int j=2; j<=aa; j++){
            if (i % j == 0){ 
                isPrime = false;
                break;
            }
        }
        if(isPrime){
            sum = sum.add(BigInteger.valueOf(i));
        }
        isPrime = true;
    }
    System.out.println("Sum  = "+sum); 
}

我没有遍历从 2 到 i 的所有数字，而是从 2 到 sqrt(i)，这大大改善了您的代码运行时间 :)

Answer 2

@Lrrr，回答正确。但算法可以进一步优化。看看我的 isPrime 算法。对于 200 万，您不需要 BigInteger。

    long sum = 2;// new BigInteger("2");
    for (int i=3; i<2000000; i++) {
        if(isPrime(i)) {
            sum = sum + i;//.add(BigInteger.valueOf(i));
        }    
    }
    System.out.println("Sum  = "+sum);

这是 isPrime 方法。

 static boolean isPrime(int n) {
    if (n < 2) {
        return false;
    }
    if (n == 2 || n == 3) {
        return true;
    }
    if ((n & 1) == 0 || n % 3 == 0) {
        return false;
    }
    int sqrtN = (int) Math.sqrt(n) + 1;
    for (int i = 6; i <= sqrtN; i += 6) {// loop 6 step
        if (n % (i - 1) == 0 || n % (i + 1) == 0) {
            return false;
        }
    }
    return true;
}

Answer 3

你可以用埃拉托色尼筛法，比你的效率高

1) 将2到N之间的所有数存入数组，并标记为素数

2) 从X = 2开始，将其所有的i*X(2X,3X..)标记为非素数，其中i为小于或等于N的自然数。不打X.

3) 找到下一个大于 X 的未标记的数字，然后重复该过程。如果没有这个数字，就停止。

4) 数组中剩余的数字是质数

像这样：

public static boolean[] findPrimes (int N) {

    boolean[] primes = new boolean[N + 1];

    // assume that all numbers are prime within given range
    for (int i = 2; i <= N; i++) {
        primes[i] = true;
    }

    // for all numbers in range, starting from 2
    for (int i = 2; i*i <= N; i++) {

        // mark natural multiples of i as nonprime
        if (primes[i]) {
            for (int j = i; i*j <= N; j++) {
                primes[i*j] = false;
            }
       }

 return primes;
}

5) 迭代返回的素数和 TRUE 值的求和索引

Answer 4

一个有效的解决方案可能是使用 Sieve of Eratosthenes 找出哪个数字是低于 2,000,000（或任何其他数字）的质数，然后 post- 处理并对它们求和：

    int n = 2000000;
    boolean[] isPrime = new boolean[n];
    //preprocess - set up the array
    for (int i = 2; i<n;i++) isPrime[i] = true;
    //run sieve:
    for (int i = 2; i < (int) Math.sqrt(n) + 1; i++) { 
        if (isPrime[i]) {
            for (int j = 2; j*i < n; j++) isPrime[i*j] = false;
        }
    }
    //sum primes:
    long sum = 0;
    for (int i = 2; i < n; i++) { 
        if (isPrime[i]) sum+=i;
    }
    System.out.println(sum);

与一次检查每个数字是否为素数相反（这需要 O(sqrt(n)) - 通过对所有数字执行此操作，您会得到 O(nsqrt(n))，在这里您可以汇总知识从以前的迭代中，有效地将复杂性降低到 O(nloglog(n))，对于足够大的 n 值，这明显更快。
这需要额外 O(n) 的成本 space。

Answer 5

到目前为止，还没有人真正正确地实施过 Sieve。仔细检查维基百科页面并注意你是如何循环数字的。如果不使用 int （或布尔值）数组进行任何优化，它应该只需要几秒钟 Java.

Answer 6

我开发了自己的解决方案，它在 700 毫秒内完成查找所有低于 200 万的内容。

我使用迭代方法，但我只是停止寻找大于 (n/i)+1 的数字，其中 n 是要检查的数是否为质数，i 是迭代循环中的数以查看它是否是除数。

public void run () {
    long sumOfPrimes = 2;
    int maxNumber = 2000000;
    int counter = 0;

    for (int i = 3; i <= maxNumber; i = i+2) {
        if(isPrimeOptimized(i)){
            sumOfPrimes = sumOfPrimes + i;
            counter ++;
        }
    }
    System.out.println("num of primes is " + counter);
    System.out.println("sum of primes is " + sumOfPrimes);
}

private boolean isPrimeOptimized(int n){
    int limitToDivide = n;
    for(int i=2;i<=limitToDivide && i<n;i++){
        if(n%i == 0)
            return false;
        else
            limitToDivide = (n/i) + 1;
    }
    return true;
}

求两个以下所有质数的总和 million.My 程序不适用于非常大的数

Find the sum of all the primes below two million.My program doesn't work for very big numbers

java

algorithm

primes