素數總和低於200萬。 Eratosthenes的篩子

解決一些小問題問題：「計算低於200萬的素數總和」。我正在使用「Eratosthenes篩」方法。我的方法工作正常，直到找到幾百個素數，但當我試圖找到總數達到2,000,000時，我得到了一個不正確的答案。素數總和低於200萬。 Eratosthenes的篩子

#include <iostream> 

using namespace std; 
long long unsigned int number[2000008]; 
int x=2000000LLU; 
int sum() 
{ 
    int s=0LLU; //stores sum 
    for(int y=2; y<=x; y++) //add all the numers in the array from 2 to 2 million 
    { 
     s+=number[y]; 
    } 
    return s; 
} 

int main() 
{ 
    int k=2; 
    for(int i=2; i<=x; i++) //fills in numbers from 2 to 2 million in the array 
    { 
     number[i]=i; 
    } 
    for(int j=2; j<=x; j+=1) //starts eliminating multiples of prime numbers from the grid 
    { 
     if(number[j]!=0) //moves through the grid till it finds a number that hasnt been crossed out. ie. isnt zero        
     { 
      for(int y=j+j; y<=x; y+=j) //when it finds a number, it removes all subsequent multiples of it 
      { 
       number[y]=0; 
      } 
     } 

    } 
    cout<<endl<<"done"; //shows that the loop has been completed 
    cout<<sum(); //outputs the sum of the grid 
    return 0; 
}

來源

2011-05-30 viraj

我不確定int是否足以保存答案......它可能比32位值大。全程嘗試使用long long。

來源

2011-05-30 12:17:22

這足以爲我存儲解決方案。 – aligray 2011-05-30 12:21:45

@aligray：這取決於你的'int'的大小，它依賴於平臺。「long」同樣適用，而「long long」應該能夠在任何平臺上保持至少64位。答案是一個38位的值。 – 2011-05-30 12:29:51

@omrib哎呀，意思是說'長'就夠了。 – aligray 2011-05-30 12:33:41

通過有效利用Sieve of Eratosthenes，我解決了這個問題，這裏是我的代碼，它是高度優化

public class SumOfPrime { 

    static void findSum() 
    { 
     long i=3; 
     long sum=0; 
     int count=0; 
     boolean[] array = new boolean[2000000]; 
     for(long j=0;j<array.length;j++) 
     { 
     if((j&1)==0) 
      array[(int)j]=false; 
     else  
     array[(int)j]=true; 
     } 
     array[1]=false; 
     array[2]=true; 
     for(;i<2000000;i+=2) 
     { 
      if(array[(int)i] & isPrime(i)) 
      { 
       array[(int)i]=true; 
       //Sieve of Eratosthenes 
       for(long j=i+i;j<array.length;j+=i) 
        array[(int)j]=false; 
      } 
     } 
     for(int j=0;j<array.length;j++) 
     { 
      if(array[j]) 
      { 
      //System.out.println(j); 
      count++; 
      sum+=j; 
      } 
     } 
     System.out.println("Sum="+sum +" Count="+count); 
    } 
    public static boolean isPrime(long num) 
    { 
     boolean flag=false; 
     long i=3; 
     long limit=(long)Math.sqrt(num); 
     for(;i<limit && !(flag);i+=2) 
     { 
      if(num%i==0) 
      { 
       flag=false; 
       break; 
      } 
     } 
     if(i>=limit) 
     flag=true; 
     return flag; 
    } 

    public static void main(String args[]) 
    { 
     long start=System.currentTimeMillis(); 
     findSum(); 
     long end=System.currentTimeMillis(); 
     System.out.println("Time for execution="+(end-start)+"ms"); 
    } 

}

和輸出

Sum=142913828922 Count=148933 
Time for execution=2360ms

，如果您有疑問，請告訴

來源

2012-12-07 13:25:13

素數總和低於200萬。 Eratosthenes的篩子

回答

相關問題