Some trouble with a prime generator

Muster Mark · 10-01-2009, 07:49 PM

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

vishnukumar · 10-01-2009, 08:01 PM

ouch!! sorry

read it wrongly

zacs7 · 10-01-2009, 08:02 PM

> 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

Muster Mark · 10-01-2009, 08:24 PM

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.

Muster Mark · 10-01-2009, 10:07 PM

Quote:

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?

arpsmack · 10-01-2009, 11:25 PM

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.

Muster Mark · 10-05-2009, 11:31 AM

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

10-01-2009, 07:49 PM	#1
Muster Mark Registered User Join Date: Sep 2009 Posts: 7	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).
Muster Mark is offline

10-01-2009, 08:01 PM	#2
vishnukumar Registered User Join Date: Sep 2009 Posts: 6	ouch!! sorry read it wrongly
vishnukumar is offline

10-01-2009, 08:02 PM	#3
zacs7 Woof, woof! Join Date: Mar 2007 Location: Australia Posts: 3,139	> 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 __________________ "I.T. gets the chicky-babes" - M. Kelly bakefile \| vim Last edited by zacs7; 10-01-2009 at 08:11 PM.
zacs7 is offline

10-01-2009, 08:24 PM	#4
Muster Mark Registered User Join Date: Sep 2009 Posts: 7	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.
Muster Mark is offline

10-01-2009, 11:25 PM	#6
arpsmack Registered User Join Date: Jan 2008 Posts: 276	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.
arpsmack is offline

10-05-2009, 11:31 AM	#7
Muster Mark Registered User Join Date: Sep 2009 Posts: 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).
Muster Mark is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Prime Number Generator	abachler	Contests Board	73	10-23-2009 07:27 AM
Calculating prime factor of a huge number.	Bakster	C Programming	15	02-20-2009 12:06 PM
prime number program with function	mackieinva	C Programming	17	09-20-2007 08:36 AM
NAQ: Everything you never wanted to know about CPP	evildave	C Programming	21	12-12-2005 10:56 AM
Prime Number Generator... Help !?!!	Halo	C++ Programming	9	10-20-2003 07:26 PM