Huge Array Problem

**torqu3e** · 01-17-2007

I wrote this code for generating loads of prime numbers.

Code:

#include<stdio.h>
#include<conio.h>
#include<math.h>
void main()
{
long unsigned int limit=4294967294;
long unsigned int n,i,flag,j=1;
clrscr();
for(n=2;n<limit;n++)
{
flag=1;
if(n==2)
{
printf("2");
continue;
}
else
{
if(n%2==0)
continue;
}
for(i=3;i<=sqrt(n)+1;i+=2)
{
if(n%i==0)
{
flag=0;
break;
}
}
if(flag==1)
{
j++;
printf("%luth prime is %lu\n",j,n);
}
}
getch();
}

It took 10 minutes on an AMD 64 BIT 2800 with 1 GB of Ram to get 250,000 primes.

Now I know that everytime the prime is outputted to the screen it slows the program, so wanted to store the primes in an array.

I created an array like this:

Code:

long unsigned int n,i,flag,j=1, a[4294967293];

I get an error saying Array should have atleast one value.

If i reduce the array size to say a[10000], it works fine.

What could be the issue?

**Niz** · 01-17-2007

well i dont know about unsigned ive only learnt about signed but the range of signed is -+32,768 for int

you should use float.

**manutd** · 01-17-2007

You realized that if an int is 2 bytes you've just taken up 8589934586 bytes (8192 MB or 8 GB) of memory! (Not to mention the other problems with your code).

**vart** · 01-17-2007

Originally Posted by Niz

well i dont know about unsigned ive only learnt about signed but the range of signed is -+32,768 for int

you should use float.

On most platforms int is a little bit longer

**manutd** · 01-17-2007

Also, using float would make no difference.

**torqu3e** · 01-17-2007

I get that memory part, tell me the other problems please, the above program runs fine so i presume it is right, the primes being given as output are also right, i have checked them.

**Salem** · 01-17-2007

Step 1 would be to learn about indentation, then read the FAQ on why void main is wrong.

**vart** · 01-17-2007

don't use conio.h and replace getch by other standard input function to prevent closing the window

**QuestionC** · 01-17-2007

The following web tool is worth giving a shot... your code seriously needs some beautification.
http://www.tote-taste.de/X-Project/beautify/

The literal error message from your compiler would be useful.

It is possible that even though you are on a 64 bit computer, you are using a 32 bit compiler, which would mean your array must be less than 4,294,967,295 bytes long.
Assuming that unsigned long ints on your sytem are 4 bytes long, you should do this:

Code:

unsigned long int a[1073741823]; // Biggest possible array of 4 byte ints in 32 bit compiler

If that doesn't work, try cutting it in half.

Incidentally, you should be hiitting your limit around the 500,000,000th prime.
And the time it takes to print to screen is definitely not going to meaningfully slow down your program. It's slow because of the amazing number of divisions your program has to perform.

**simguy** · 01-17-2007

Your unsigned int array is going to consume over 30 GB of memory!! long int is 4 bytes ! Unless you have access to a super computer, this will never work. You already stated that you got about 250,00 primes --- why do you need a 4 GB array to hold so many fewer values? You might want to break this down into separate programs to run a range of values instead of running 4 GB worth at one time.

**anon** · 01-17-2007

I don't know you algorithm, but you shouldn't need more than int prime[25000] for 25000 primes.

To find them, you'll just need to check-divide each (odd) number with the primes that you have found so far. If it is not evenly divisible by any of these, it's a prime (if a number is divisible by 9, it is also divisible by 3 - a prime -, so you won't need to test separately if it can be divided by 9 - or any other non-prime). So the only thing you need to keep in memory - in addition to a few variables - is an array of previously found primes.

For me, actually printing 25000 values to screen is a problem. The beginning of the output is lost for ever... and it takes much longer to print them than to find them. The 25000th I got was 287,117, though. (If you were using something like a Sieve of Erosthrates you would need an array of 287,117 flags, but you have no way of knowing that before you solve the problem.)

**quzah** · 01-17-2007

The 250000th prime is not 287117. That would mean something like 87% of all numbers between 1 and 287117 were prime, which clearly is not the case, since half of them are even numbers!

Quzah.

**Dave_Sinkula** · 01-17-2007

Originally Posted by torqu3e

It took 10 minutes on an AMD 64 BIT 2800 with 1 GB of Ram to get 250,000 primes.

Unless you're a fast reader, wouldn't it serve you better to write to a file? You could probably just pipe the output of your original (and give you a further excuse to ditch getch) to a file and open it in an editor much more quickly.

@Quzah: 25000/250000

**torqu3e** · 01-18-2007

anon, that algorithm finds some numbers known as pseudo primes, thats why you are getting so many primes in such a short range.

Vart i will switch to "while(!kbhit());" instead of getch();

If i use a[2147483647] for the array it says "Array size too large"
If i use a[4294967294] for the array it says "Array must have atleast one element"

**vart** · 01-18-2007

Originally Posted by torqu3e

If i use a[2147483647] for the array it says "Array size too large"
If i use a[4294967294] for the array it says "Array must have atleast one element"

Seems to be explicit conversion of the array index to the int type

Thread: Huge Array Problem

Thread Tools

Search Thread

Display

Huge Array Problem

Similar Threads

simple array of char array problem

Quick question about SIGSEGV

Struct *** initialization

Help with an Array

From stream/file to a string array problem