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.**

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.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;

}

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).