Project Euler Problem 10

[simpleasy]

Hi everyone,

I think most people here are familiar with project Euler, if not, here is a link: http://projecteuler.net/problem=10

I already made a working code for this problem (Problem 10), but it took about an hour before it was done calculating.
So I did a little research on the internet and found out about the sieve of Eratosthenes. So I made a program that would calculate the answer to this problem in this manner. It works fine on smaller numbers, but it crashes when I input 2 million, and it gives a negative result at 1 million, so I'm guessing it has something to do with the variablesize being too small, though I have no idea how to fix it...

here is the code:

void Problem10()
{
	/* 
	** The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
	** 
	** Find the sum of all the primes below two million.
	*/

	using namespace std;
	const int n = 2000000; //highest number tested
	char prime[n];
	memset(prime,0,n);
	for(int p=2; p <= (int)sqrt((double)n); p++)
	{
		if (prime[p-1] != 1)
		{
			for(int q=p*p; q <= n; q += p)
				prime[q-1] = 1;
		}

	}
	int nTotal = 0;
	for (int p=2; p <= n; p++)
	{
		if (prime[p-1] != 1)
		{
			nTotal+=p;
		}
	}
	cout << endl << nTotal << endl;
}

int main()
{
	Problem10();
	return 0;
}

[coder777]

Line 11 doesn't compile with conform C++.

2000000 likely bursts the stack (when writing to a higher number in the array).

[kbw]

This declares your bool array on the stack:

	const int n = 2000000; //highest number tested
	char prime[n];

The stack is a scarce resource, so you should consider allocating large blocks of memory like that from the heap.

Part of the problem with the stack is that the size is determined by the linker, and not the compiler so you just don't know how large it is. In your case, you know the context in which your function is called, but in general you don't know. So even if you're code's run in an environment where there's plenty of stack space, you could be called when a lot of it is already used. So it is really important to use as little stack as is reasonable, and avoid the use of alloca().

Also, as the number of primes in a fixed range decreases as the numbers get larger, it may be more efficient to store the actual prime numbers rather than storing a flag against a huge range of numbers. Of course, this particular algorithm doesn't lend itself to that naturally.

[simpleasy]

I had never heard of the heap and the stack, until now. After changing the code a little bit, the program doesn't crash anymore.
I changed line 11 to:
char *prime = new char[n];

and I also changed nTotal to a long long, instead of an integer. (since I noticed 4 bytes wouldn't be enough)

this gave me the correct result. Thank you for your help everyone :)