Stack Overflow

[GRex2595]

Can anyone make any suggestions to make this code more efficient so that it doesn't cause a stack overflow? I think it's my humongous array, but I don't think I can change that without drastically reducing speed.

This code is for Problem 10 of Project Euler.

#include <iostream>
#include <cmath>

using namespace std;

bool add(int [], int);
void display(int []);

int main()
{
	//declare variables
	int primes [500000];
	int end = 0;
	int result [15] = {0};

	for(int x = 2; x < 2000000; x++)
	{
		bool prime = true;

		for(int y = 0; y < end; y++)
		{
			if(primes[y] > sqrt(double(y)))
				break;
			if(x % primes[y] == 0)
			{
				prime = false;
				break;
			}//end if
		}//end for

		if(prime)
		{
			if(end == 500000)
			{
				cout << "Array resizing needed\n";
				return 0;
			}//end if
			primes[end] = x;
			if(!add(result, x))
			{
				cout << "Array resizing needed\n";
				return 0;
			}
			end++;
		}//end if

		
	}//end for

	display(result);

return 0;
}//end main

bool add(int arr[], int num)
{
	//declare variables
	int tran [15];

	for(int x = 14; x >= 0; x--)
	{
		if(num == 0)
			break;
		tran[x] = num % 10;
		num / 10;
	}//end for

	for(int x = 15; x >= 0; x++)
	{
		arr[x] = tran[x] + arr[x];
		if(arr[x] > 9)
		{
			if(x = 0)
				return false;
			int temp;
			temp = arr[x] / 10;
			arr[x - 1] += temp;
			arr[x] -= temp * 10;
		}//end if
	}//end for

	return true;
}//end add
void display(int arr[])
{
	//declare variables
	bool first = false;

	cout << "Result:  ";
	for(int x = 0; x < 15; x++)
	{
		if(arr[x] != 0 && !first)
			first = true;
		if(first)
			cout << arr[x];
	}//end for
	cout << endl;
}//end display 

[naraku9333]

You are really over thinking this. You only need to keep the sum of the primes, you dont need the prime numbers themselves. I'll try to give you some pseudo code so not to ruin it for you.

loop from 3 to 2000000
    is this number prime?
        add to sum
output sum

The loop can be optimized a bit, but get a working version first.
Edit: fixed some typos.

[GRex2595]

I don't want to have to make a whole bunch of tests for this if I can just clear all the prime numbers. A number cannot be made without a prime number unless the number itself is prime, so I want to only check prime numbers to see if the number is prime. Having to check a whole bunch of numbers that will result in the same as any prime takes a lot more time than necessary, That's why I want to have that array for keeping the primes.

[naraku9333]

so I want to only check prime numbers to see if the number is prime

I have no idea what you mean here. If you mean only checking numbers with the properties all primes share (only thing I can think of is all primes are odd).

[GRex2595]

I only want to use prime numbers to decide whether or not a number is prime.

[GRex2595]

Currently using a text file to store the numbers and it is 1.19 MB

EDIT: More efficient program only needs 1.11 KB of memory for the file.

[JLBorges]

Use a sieve algorithm, perhaps?

#include <bitset>
#include <iostream>

int main()
{
    enum { N = 2 * 1000 * 1000 } ;

    static std::bitset<N> sieve ;
    sieve = ~sieve ;
    for( std::size_t i = 2 ; i < N ; ++i ) if( sieve[i] )
          for( auto j = i*i ; j < N ; j += i ) sieve[j] = false ;

    long long sum = 0 ;
    for( std::size_t i = 2 ; i < N ; ++i ) if( sieve[i] ) sum += i ;
    std::cout << sum << '\n' ;
}

[GRex2595]

I don't understand that code. Now I completely revamped my code and got the same answer in significantly less time, but I still can't get the right answer for some reason.

I'm not sure what's wrong.

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
	//declare variables
	int result = 2;
	int root;

	for(int x = 3; x < 2000000; x += 2)
	{
		root = sqrt(double(x));

		bool prime = true;

		for(int y = 2; y <= root; y++)
		{
			if(x % y == 0)
			{
				prime = false;
				break;
			}//end if
		}//end for

		if(prime)
			result += x;
	}//end for

	cout << result << endl;

return 0;
}

[Phil123]

There's something seriously wrong with variable result. When you fix that, you'll get the correct answer (I know, because I just did). Happy logical thinking ^^

[GRex2595]

Did you get 1179908154? I have gotten that every time and I can't figure out what's wrong with that.

EDIT: Nvm, I got the answer after making it a long long.

[helios]

The correct answer is 142913828922, which requires at least 38 bits to be exactly represented. Your implementation likely uses 32-bit integers, so you're causing an overflow when trying to calculate such a large number.
Try using long long.

PS: Your loop over y can be made twice as fast this way:
for(int y = 3; y <= root; y+=2)

[Volatile Pulse]

I had the same exact issue, but I created a vector to store all of my prime numbers. It runs fairly quickly, a few seconds, on my desktop. It took me posting here as well to figure out what my issue was as well. I never would have imagined something that seemed so simple would overflow.

[ne555]

Regarding the original question

I want to only check prime numbers to see if the number is prime.

Your array is over sized.
To know all the primes that are less that 100 you only need the primes that are less than 10. (it applies to the sieve too)
Besides that, there are approx log(n) primes that are less than n.

if(primes[y] > sqrt(double(y))) break; ¿what? (line 22)

[GRex2595]

I wasn't thinking when I wrote that. I meant to break if it was larger than the square root of y. Anyways, I eventually tried fstream and got way more than necessary. The file is 1.19 MB and the program takes about 15 minutes. The code above took seconds.

Thanks for all your help everybody. If you want to help on my new problem (Problem 13) I'm having issues with the result.

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

void add(int [50][100], int [70]);
void display(int [70]);

int main()
{
	//declare variables
	int nums [50][100];
	int result[70] = {0};
	ifstream read;
	string input;

	read.open("Euler.txt");
	if(!read.is_open())
	{
		cout << "Could not open Euler.txt\n";
		return 0;
	}//end if

	for(int y = 0; y < 100; y++)
	{
		getline(read, input);
		
		for(int x = 0; x < 50; x++)
		{
			stringstream(input.substr(x, 1)) >> nums[x][y];
		}//end for
	}//end for

	read.close();

	add(nums, result);
	display(result);

return 0;
}//end main

void add(int nums[50][100], int result[70])
{
	for(int x = 49; x >= 0; x--)
	{
		for(int y = 0; y < 100; y++)
		{
			result[x + 20] += nums[x][y];
		}//end for
	}//end for

	for(int x = 69; x >= 0; x--)
	{
                //I think the problem is right in here
		result[x] = result[x] % 10;
		if(x > 0)
			result[x - 1] += result[x] / 10;
	}//end for
}//end add
void display(int result[70])
{
	//declare variables
	bool first = false;
	int x = 0;

	for(int digit = 0; digit < 10; digit++)
	{
		if(result[x] != 0)
			first = true;
		//end if

		if(first)
			cout << result[x];
		else
			digit--;
		//end if
		x++;
	}//end for
	cout << endl;
}//end display 

[GRex2595]

Figured out main problem in the code above.

[JLBorges]

> I don't understand that code.

Sieve of Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes