Help w/ prime # determination

crystalattice · #1 12-Apr-2004, 18:53

What started out as a simple project is giving me headaches. The task is to write a C program the outputs x prime numbers, where x is a value input by the user. My problem is that rather than stopping after the program loops x times, it stops when the prime number = x. For example, if you want to see 3000 prime numbers, the program stops after 431 iterations when the prime number is 2999. I've been told that instead of incrementing my input variable w/ every loop cycle, it should only increment when a prime number is found, but I can't figure out how to do that.

Below is the main file and the function.

CPP / C++ / C Code:

#include "primes.h"

int main()
{
	int see, input, i=0;
	
	printf("%s\n%s",
		"PRIMES WILL BE PRINTED.",
		"How many do you want to see?  ");
	scanf("%d", &see);
	for (input = 0; input <= see; ++input)
		if (is_prime(input)==1){     /*if a prime is found, increment a counter then print the counter and the prime number*/
			++i;
			printf("%d:\t%d\n", i, input);
		}
	return 0;
}

CPP / C++ / C Code:

#include "primes.h"

int is_prime(int n) /*'input' is passed to function as 'n'*/
{
	int k, limit;
	
	if (n==2) /*if 'input' = 2, then it's prime and 'true' is returned*/
		return 1;
	if (n%2==0) /*if 'input' is evenly divisible by 2, then it's not prime and 'false' is returned*/
		return 0;
	limit = n/2;
	for (k=3; k <= limit; k += 2) /*checks to see if 'input' is evenly divided by an odd #*/
		if (n%k==0)
			return 0;
	return 1;
}

Thanks for any new ideas on this.

Max Payne · #2 12-Apr-2004, 19:56

change this loop:

for (input = 0; i < see; ++input)

the condition i<see is what u should do because you want to loop until the number of see is reached that is the number of primes "i".

Max Payne · #3 12-Apr-2004, 19:59

And here is a better way to determine wether a number is prime or not:

The number is not prime when:
(n-1)%6!=0 and (n+1)%6!=0

hope this helps. ;-)

WaltP · #4 13-Apr-2004, 01:43

Quote:

Originally Posted by Max Payne

change this loop:

for (input = 0; i < see; ++input)

the condition i<see is what u should do because you want to loop until the number of see is reached that is the number of primes "i".

Correct.

Another possibility is to simply output 2 as prime then start your loop and skip even numbers:

Code:

for (input=3, i=1; i  < see; input+=2)

This will start input at 3, i at 1 (for the 2), and skip all even numbers.

Also, the max number you need to check for a prime is sqrt(value) instead of value/2. Play around with some tests and you'll see why.

crystalattice · #5 13-Apr-2004, 18:33

I finally got it working. I knew it was a simple fix but just couldn't see it. I really appreciate the quick responses. I hope that I will soon be able to offer my own advice to others, as soon as I learn a little more.

Thanks again!

machinated · #6 14-Apr-2004, 13:02

yes skipping evens would be much more efficient! good idea walt! i was wondering if one could use bitshifting in some way instead of modular division to make it even more efficient!

WaltP · #7 14-Apr-2004, 17:55

Quote:

Originally Posted by machinated

yes skipping evens would be much more efficient! good idea walt! i was wondering if one could use bitshifting in some way instead of modular division to make it even more efficient!

Personally, I would consider that level of "efficiency" a waste of time unless you are dealing with extremely huge numbers. But then you'd also be dealing with non-standard integers (16- or 32-byte -- yes byte -- integers.) Then these tricks might be useful, but not for standard types as defined in current systems.

It would also be hard to understand the code because of the obfuscation. Therefore, not recommended on that level either.

Max Payne · #8 14-Apr-2004, 19:34

Quote:

Originally Posted by machinated

yes skipping evens would be much more efficient! good idea walt! i was wondering if one could use bitshifting in some way instead of modular division to make it even more efficient!

Hi machinates,

Can you explain to me what is bitshifting is. I am constantly searching for a good algo to generate prime number. Maybe this could help me. Thanks.

sdeming · #9 14-Apr-2004, 20:01

Quote:

Originally Posted by Max Payne

Hi machinates,

Can you explain to me what is bitshifting is. I am constantly searching for a good algo to generate prime number. Maybe this could help me. Thanks.

If you are looking to generate a single prime number then a combination of efforts can be used. If you want to generate a range, starting from 1 you should look at the Sieve of Erastothenes. It's rather nifty.

Consider this. You have a huge bitset, all turned off. You initialize your bitset by turning on 1 and 2 (also store these or print these out as primes) and this is where the fun begins. Not iterate through the entire bitset in multiples of 2 (4, 6, 8, 10, ...) and turn the bits on. Now from this point forward, you increment by 1 (we're now at three) and if the bit is off then the number is prime, store it or print it. Now iterate through all multiples of this prime (6, 9, 12, 15 ...) and turn the bits off. Increment again and we're at 4, which was turned off when iterating through multiples of 2. Skip it and move on to 5 which is off. Remember, any time you encounter an off during the main loop, you are on a prime. Display or store 5 and iterate through all multiple of 5, turning the bits off. Increment to 6, it's a multiple of 2 so it's already off. Next is 7, it's off and prime, display or store and iterate through it's multiples and turn them all off. Continue until you fill your field.

This sieve is pretty nifty but it does require a good deal of memory to build a sizable list of primes. But you may notice that there are no divides or mods here at all. It's all increments and muls.

Max Payne · #10 15-Apr-2004, 01:09

Quote:

Originally Posted by sdeming

If you are looking to generate a single prime number then a combination of efforts can be used. If you want to generate a range, starting from 1 you should look at the Sieve of Erastothenes. It's rather nifty.

Consider this. You have a huge bitset, all turned off. You initialize your bitset by turning on 1 and 2 (also store these or print these out as primes) and this is where the fun begins. Not iterate through the entire bitset in multiples of 2 (4, 6, 8, 10, ...) and turn the bits on. Now from this point forward, you increment by 1 (we're now at three) and if the bit is off then the number is prime, store it or print it. Now iterate through all multiples of this prime (6, 9, 12, 15 ...) and turn the bits off. Increment again and we're at 4, which was turned off when iterating through multiples of 2. Skip it and move on to 5 which is off. Remember, any time you encounter an off during the main loop, you are on a prime. Display or store 5 and iterate through all multiple of 5, turning the bits off. Increment to 6, it's a multiple of 2 so it's already off. Next is 7, it's off and prime, display or store and iterate through it's multiples and turn them all off. Continue until you fill your field.

It look like a good algo, but I it increases the number of loops and if the number gets bigger, the number of loops also increase dramatically..is it ok??

Quote:

Originally Posted by sdeming

This sieve is pretty nifty but it does require a good deal of memory to build a sizable list of primes. But you may notice that there are no divides or mods here at all. It's all increments and muls.

does division or mod consumes more calculation time than increments and muls??

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Help w/ prime # determination

Thanks for the help!