# Thread: Some trouble with a prime generator

1. ## Some trouble with a prime generator

Hello everyone,

My Background: I am a novice C programmer. I simply bought a book* and am trying to teach my self out of general interest in computer science.

My Trouble: As an exercise, I tried to write a program that would give the user the n'th prime number when given n. I thought I had worked out all the kinks when I found a bug that I just can't fix: for very large input the output is lower than it should be. I know this happens for 174,440,041 to be precise, and the output is 3,619,045,627 but it should be 3,657,500,101.**
Code:
```#include <stdio.h>
#define SIZE 2000029
int main (void)
{
unsigned long long int Num;
int Count, R, Lim, Test;
char Flag;
int Primes[SIZE];
printf("Enter the n'th prime you want to see.\n");

while(scanf("%d", &Lim)==1)
{
Flag=0;
Num=2;
Count=0;
Test=0;
Primes[0]=2;
while(Count<Lim)
{
for(Test=0,R=1;R!=0&&Primes[Test]*Primes[Test]<Num;Test++)
{
Flag=1;
R=Num%Primes[Test];
}
if(R==0)
Num+=Flag+1;
else
{
if(Count<SIZE)
{

if(Primes[Test]*Primes[Test]>Num)
{
Primes[Count]=Num;
Num+=Flag+1;
Count++;
}
else
Num+=Flag+1;
}
else
{
if(Primes[Test]*Primes[Test]>Num)
{
Count++;
Num+=Flag+1;
}
else
Num+=Flag+1;
}
}
}
if(Num<=4)
printf("\n\n%llu\n\nEnter q to quit, or another number to see another prime.", --Num);
else
printf("\n\n%llu\n\nEnter q to quit, or another number to see more primes.", Num-2);
}

return 0;
}```
My Attempts At Solving: This behavior indicates to me that the program is concluding that numbers are prime that aren't, and thus finishing it's count prematurely. The only reason I can think of for this to happen is that SIZE is too small, and thus it runs out of prime numbers to use as tests, concluding a number is prime that merely has as its smallest factor a number larger than the 2000029'th prime (32,453,321). This can't be, however, because what I get as output (3,619,045,627) is much, much smaller than the 2000029'th prime squared (1,053,218,043,929,041). I have confirmed that the program works correctly for the input 9,737,333, (and I assume this means all values lower) so it's not simply failing for input larger than SIZE. Also, the max value for a long long unsigned int is 2^64 (right?) which is also much, much greater than the answer it should be giving me, so it's not looping around on me.

Thanks for reading this. Although there is no material reason for me to solve this quandary, I am rather frustrated by it, and am immensely grateful for any help.
-------------------------------------
*C Primer Plus by Prata (recommended by a friend) 2nd ed.
**Since it takes many hours for computations of this size, I haven't run many tests, and thus don't know the exact edge of where it starts counting non-primes as primes (which I assume it's doing to cause the problem).

2. ouch!! sorry

3. > Also, the max value for a long long unsigned int is 2^64 (right?) which is also much, much greater than the answer it should be giving me, so it's not looping around on me.
At least (2^64) - 1 as required by ANSI. So that's 18,446,744,073,709,551,615 not 18,446,744,073,709,551,616.

My guess is you're still overflowing somewhere. You could try set some conditional breakpoints (see your debugger) and let it run overnight in an attempt to see where that happens. I'm guessing it's with "Num".

BTW,
Code:
```#define SIZE 2000029

...

int Primes[SIZE];```
Primes is enormous for the stack, (200029 * 4) = 800116 bytes (assuming an int is 4 bytes), which is ~ 7.5MB. Which is much larger that most compilers allow (typical stack space is 2MB). Not your problem, but something to be aware of -- see malloc().

PS: Not a fan of the variable names

4. Thanks for the prompt reply!

Overflow sounds pretty likely now that you mention it. But it still doesn't really make sense, because which variable could be overflowing? Regardless, I will now run some tests to that regard (I haven't figured out the debugger of Xcode yet *smiles embarrassedly* so I will assign all variable as long long type, this will work right?).

About the stack: thanks for pointing this out, as I've never really understood why I couldn't have size be 3000000 (it would compile using gcc, but I would get a segfault error if I ran it). Is the stack stored in the L2 cache?

Thanks again.

P.S. Last time I tried to change variable names in a program, it took an inordinate amount of time do to incessant typos, so forgive me if I don't fix them.

5. Originally Posted by zacs7
>
My guess is you're still overflowing somewhere. You could try set some conditional breakpoints (see your debugger) and let it run overnight in an attempt to see where that happens. I'm guessing it's with "Num".
...
Why would Num be overflowing, given that it's maximum value is so large compared to the numbers it could be?

6. Num is unlikely to overflow, but you routinely compare it to Primes[Test] * Primes[Test], which seems like a possible candidate for overflow. I would check to see if that's your problem. Cast to long long before doing the multiplication.

7. ## Yay, it worked!

Thanks so much! putting (unsigned long long int) in front of Primes[Test] worked wonderfully! And, best of all, I only melted one computer in verifying this(fortunately, not a valuable one).