Sum of primes below two million. Sieve of Eratosthenes
Having a little trouble solving Problem: 'Calculate the sum of primes below two million'. I'm using the 'Sieve of Eratosthenes' method. My method works fine for finding primes till hundred but when I try to find the sum of primes till 2,000,000 I get an incorrect answer.
#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
开发者_C百科 {
number[y]=0;
}
}
}
cout<<endl<<"done"; //shows that the loop has been completed
cout<<sum(); //outputs the sum of the grid
return 0;
}
I'm not sure an int is enough to hold the answer... It could be larger than a 32-bit value.
Try using long long
throughout.
by using Sieve of Eratosthenes effectively, i solved the problem, here is my code , it is highly optimized
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");
}
}
and the output is
Sum=142913828922 Count=148933
Time for execution=2360ms
if you have doubt, please do tell
精彩评论