Prime number, allocated memory and processing power..

[salies1807]

So, I am a beginner and as exercise I wrote a code to show all prime number up to the input. It worked pretty well, but then I wanted to see up to which number could my computer process in a resonable amount of time. I got into two problems. First, at least on my pc, the maximum array size that I can create without crashing is exactly 519.371(i.e.:array[519371]). And second, making some ajustments I actually could allow an input for which my pc couldn't calculate in a relative small time, even though around 40% ,peaking 50% sometimes, of the processor was doing this task. To calculate the primes in between 2 and 5.000.000 - without any other things being done - my pc took
4 minutes and 38 seconds.

Said so, this are my questions:

1.Is there any way to expand the maximum size of arrays? Maybe allocating more memory for it? I need it because the array I'm using is actually to store the primes in order to calculate the next, and am too lazy to try to use two arrays.

2.Is there any way to expand the processors usage to make the code faster?
No overclocking solution.

Code:

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main ()	{
	
	int n, l=3, x=2, j, d;
	
	cout << "Choose up to which number would you like to know the prime numbers.";
	cout << "\nThe maximum input is 5.000.000, and the minimum is 5: ";
	cin >> n;
	cout << endl << endl;
	
	while (n>5000000||n<5)  {
		
	cout << "Invalid input, try again: ";	
	cin >> n;
	cout << endl << endl;
		
	}
	
	int Primos[int (ceil(n/(log (n)-1.1)))];
	Primos[2]=2;
	cout << "2\t";	
	
	do	{
		
		j=2;
		
		do	{
			
			d=l%Primos[j];
			++j;
									
		}	while (x-j>=0&&d!=0&&Primos[j]<=l/2);
		
		if (d!=0)	{
			
			cout << l << "\t";
			++x;
			Primos[x]=l;
			
		}
	
		l = l + 2;
				
	}	while (n>l-1);
	
	cout << endl << endl << "Finished" << "\n\n";
	cout << "Number of primes: " << (x-1) << "\n\n";
	
	system("Pause");		
	return 0;
}

[salies1807]

Just found out that using two arrays wouldnt solve the problem. T.T

[megatron 0]

This:

int Primos[int (ceil(n/(log (n)-1.1)))];

Is allocated on the stack, so what? 519.371 * 4 byte integers.. that's a lot of memory you are allocating on the stack. Program stack has a certain size.

You can either:

Allocate the array on the heap using new.

Or what I did, which was spitting results out to a file when I calculated x amount of primes.

As for making it faster.. I can't help much. I don't have access to my prime number calculating code as of now.

[salies1807]

Oh, cool, got it. :D
Still out of my range, though.

[megatron 0]

Out of range? Allocating on heap should allow you to create a larger array. On my system (Linux, 4gb RAM i was allowed to allocate 2GB of memory before the OS refused to give me more.

If that fails try using a vector?

If you store primes in a file, you can overwrite data in the array. Just reusing the memory.

[salies1807]

I actually meant about knowledge. I don't how to that, yet. :)