Want to create LARGE array of prime numbers(C++)

Mr. Flibble

Hi.

I am trying to create an array of prime numbers(for use in an other project) and have written a program to do this.

The program works fine for finding primes up to about 100 000(this takes c. 1min). It workes and crashes finding primes up to 1 000 000(think it took bout 30 mins) and crashes instantly when asked to find primes up to 10 000 000.

Can someone tell me how to create a larger array of primes with this program. Or of a different, better way to do it.


ps. I didn't write all this code - the messy bits were done by me! Some of the code does nothing as I have just cut and pasted it from part of a larger program.

pps. I am very new to C++ programming so pls don't laugh:-)

#include <stdio.h>
long int main(long int argc, char* argv[])
{
long int bless,HIGH = 1000,i=0,yn=0,x,Y[4000];
thestart:;
cout << "Enter upper number for primes\n";
cin >> HIGH;

if(argc == 3)

{
HIGH = atoi(argv[4000]);
}
// create and populate the array
int* p = new int[HIGH];
for(int i = 0; i < HIGH; ++i) p = i+1;

for(i = 2; i < HIGH; ) // loop through the integers, starting with 2
{
for(int j = i; j < HIGH; ++j) // loop through the array
{
if((p[j] != i) && (0 == (p[j] % i))) p[j] = 0;
}
while(p[i++] == 0); // get the next sieve - this saves a lot of processing
}
for(i = 0; i < HIGH; ++i)
{
if(p != 0)
{
Y[yn]=p;
printf("%2i",p);
x=p;
printf(" ",x);
yn++;
}
}
{
cout << "\nPrimes up to: " << HIGH <<". Highest prime: " << Y[yn-1] << ". Number of primes: "<< yn<<"\n\n";
yn=0;
goto thestart;
return 0;
end:;

}}

Trojan

Heya,

Sorry I don't have much time to look at this right now, but there's one or two things that catch my eye: either I'm not comprehending what you are doing, or you should have a look at those lines...

You say it works to some degree

Also if you could post it up correctly tabulated that would be nice, use the [ code ] to wrap it

[*] unimportant point: you don't need long for either main() or argc, both as int should be fine. In fact, you could have main as void.

[*] You shouldn't use goto (and the label thestart). It's quite bad practice (although handy for quick hacks). Use a loop format instead. The only valid reason for a goto is error handling.

[*] You ask for a value for HIGH then overwrite it if there was one on the command line.

I can't say anymore without formatting it so I can work out the loops and do the maths, and like I said, I don't have time just now... I think the things I've mentioned above will not have any positive effect on how the program will run though, it's a mathematical issue prolly.

hth,
Al.

Mr. Flibble

Thanks for the reply. I have cleared ut the code a bit. (I didn't write most of it and dont understand it all) - couldya tell me what the 'argc' bit is doing?

Basically it works fine with small primes(<1M) but crashes above that. Would that be because the array cant hold that much data?

#include <stdio.h>

 int main(int argc, char* argv[])
{
 int HIGH,i;
cout << "Enter HIGH(upper number for primes)\n";
cin >> HIGH;
if(argc == 3)
{
HIGH = atoi(argv[2]);
}
// create and populate the array
int* p = new int[HIGH];
for(int i = 0; i < HIGH; ++i) p[i] = i+1;

for(i = 2; i < HIGH; )	// loop through the integers, starting with 2
{
for(int j = i; j < HIGH; ++j)	// loop through the array
{
if((p[j] != i) && (0 == (p[j] % i))) p[j] = 0;
}
while(p[i++] == 0);	// get the next sieve - this saves a lot of processing
}
for(i = 0; i < HIGH; ++i)
{
		if(p[i] != 0) 
		{
		printf("%2i ",p[i]);
		}
}
}

Mr. Flibble

Thanks for the reply. I have cleared ut the code a bit. (I didn't write most of it and dont understand it all) - couldya tell me what the 'argc' bit is doing?

Basically it works fine with small primes(<1M) but crashes above that. Would that be because the array cant hold that much data?

#include <stdio.h>

 int main(int argc, char* argv[])
{
 int HIGH,i;
cout << "Enter HIGH(upper number for primes)\n";
cin >> HIGH;
if(argc == 3)
{
HIGH = atoi(argv[2]);
}
// create and populate the array
int* p = new int[HIGH];
for(int i = 0; i < HIGH; ++i) p[i] = i+1;

for(i = 2; i < HIGH; )	// loop through the integers, starting with 2
{
for(int j = i; j < HIGH; ++j)	// loop through the array
{
if((p[j] != i) && (0 == (p[j] % i))) p[j] = 0;
}
while(p[i++] == 0);	// get the next sieve - this saves a lot of processing
}
for(i = 0; i < HIGH; ++i)
{
		if(p[i] != 0) 
		{
		printf("%2i ",p[i]);
		}
}
}

Mr. Flibble

test

Void

Maybe use a linked list instead of an array? I've had problems before trying to allocate huge chunks of memory at once.

Gerry

yeah, apparently all the major security companies, like baltimore etc, use linked lists to get around the limits of ints. It makes it slower, but who cares any more, just up the minimum specs

Mr. Flibble

Please see other topic: 'Want to create LARGE array of prime numbers(C++)2'.