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