Thread: Some trouble with a prime generator

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    14

    Unhappy 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. #2
    Registered User
    Join Date
    Sep 2009
    Posts
    6
    ouch!! sorry

    read it wrongly

  3. #3
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    > 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
    Last edited by zacs7; 10-01-2009 at 08:11 PM.

  4. #4
    Registered User
    Join Date
    Sep 2009
    Posts
    14
    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. #5
    Registered User
    Join Date
    Sep 2009
    Posts
    14
    Quote Originally Posted by zacs7 View Post
    >
    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. #6
    Registered User
    Join Date
    Jan 2008
    Posts
    290
    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. #7
    Registered User
    Join Date
    Sep 2009
    Posts
    14

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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prime Number Generator
    By abachler in forum Contests Board
    Replies: 76
    Last Post: 12-06-2009, 05:08 PM
  2. Calculating prime factor of a huge number.
    By Bakster in forum C Programming
    Replies: 15
    Last Post: 02-20-2009, 12:06 PM
  3. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  4. NAQ: Everything you never wanted to know about CPP
    By evildave in forum C Programming
    Replies: 21
    Last Post: 12-12-2005, 10:56 AM
  5. Prime Number Generator... Help !?!!
    By Halo in forum C++ Programming
    Replies: 9
    Last Post: 10-20-2003, 07:26 PM

Tags for this Thread