Sieve of Eratosthenes

Feb 18, 2012 at 2:41am

Hello there. I have this in General C++, but I feel like this section gets more attention. So please pardon my repost. Im working on a euler project problem. I'm attempting to use the "sieve of eratosthenes" (on wikipedia) pseudo code. Here's my interpretation:

//euler prob_10
#include <iostream>
using namespace std;
//answer should be: 142913828922
int main(){
	int i,j,sum=0,n=2000000;
	bool list[n];
	list[0]=false;
	list[1]=false;
	for(i=2;i<n;i++)
		list[i]=true;
		
	for(i=2;i<n/2;i++){
		if(list[i]==true)
			for(j=2*i;j<=n;j+=i)
				list[j] = false;
	}
	for(i=2;i<=n;i++){
		if(list[i]==true)
			sum+=i;
	}
	cout<<sum<<endl;
	return 0;
}

Edit & run on cpp.sh

when i run a smaller max range like 10 in for n, I get the correct answer. But not with 2000000. Any help? Thanks in advance!! Could it be because of the large size of the answer (142913828922) ?

Last edited on Feb 18, 2012 at 2:44am

Feb 18, 2012 at 3:16am

cire (8284)

Very probably. Change the type of sum to unsigned long long.

Feb 18, 2012 at 8:14am

Caprico (226)

!) How did you know the answer?
2) Like cire said, use unsigned long long. Its upper limit is 2^64. Will easily serve your purpose
3) Line 8 and 9 don't seem to have any significance... Redundant code?
4) Even I'm a Euler fan, currently working on Sudoku solver.. Smart that you used Sieve of Eratosthenes. Much faster than checking each number for primeness. *respect* :)

Feb 18, 2012 at 3:13pm

jwroblewski (39)

Thanks much. I have investigated the unsigned long long, but its seems very complicated to be able to use it. Haha how did I know the answer? Lots of code of people's attempt at the problem, sometimes the answer inside the comments. I know the answer but refuse to submit it without seeing it appear at the end of my own app. Line 8 and 9 are to set numbers 0 and 1 to false, unless they come default set to false?

Thanks much for your help buds. My next question is how do I incorporate the unsigned long long?

p.s. your respect means much, but i must admit that my first attempt did involve "checking each number for primeness". Without a suggestion from another, i would probably still be waiting for my for loop to finish. :)

EDIT: Just kidding! I just wasnt declaring the type correctly. Unsigned long long int, and pop out comes my answer. Thanks guys!!

Last edited on Feb 18, 2012 at 3:21pm

Topic archived. No new replies allowed.

C++

Forum

Sieve of Eratosthenes