找到所有素數低於200萬的總和。我的程序不適用於非常大的數字

Question

這是我尋找素數總和的代碼。它適用於低數字，但如果是2000000（200萬）它永遠不會結束。任何人都可以幫助我？

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至我的號碼去我剛剛從2到開方（我），這提高代碼的運行時間很多:)

Answer 2

@Lrrr，答案是正確的。但算法可以進一步優化。看看我的isPrime算法。對於2百萬，你不需要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

你可以使用Eratosthenes的Sieve算法，它比你更有效率。

1）將數組中的所有數字存儲在2到N之間，並將它們全部標記爲素數。 2）從X = 2開始，標記其所有的i * X（2X，3X ..），其中i是自然數小於或等於N，乘數不是素數。不要標記X.

3）找到下一個數字大於未標記的X並重復該過程。如果沒有這樣的號碼，請停止。

4）的陣列中的剩餘數是素數

像這樣：

公共靜態布爾[] 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找出哪個數字在prime下面2,000,000（或Y以外的號碼），而且比後處理和總結他們都：

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)。

Answer 5

到目前爲止沒有人真正實現了Sieve。仔細檢查維基百科頁面，注意你如何循環播放數字。如果沒有使用int（或布爾值）數組進行任何優化，它在Java中只需要幾秒鐘。