Can some one tell me the algorithm or procedure of how to find prime numbers ??
Note Im not asking that how to code it just asking the way of it.
Printable View
Can some one tell me the algorithm or procedure of how to find prime numbers ??
Note Im not asking that how to code it just asking the way of it.
There are several algorithms. I quite like "Sieve of Eratosthenes" as a quite "neat" one.
Almost all other algorithms follow this principle: Take a number, try to divide by the numbers 2, 3, 5, 7, .... until square-root of number. If you "generate" odd numbers, there is no reason to try to divide by 2, of course.
The really naive approach is:
It improves performance quite a bit to only try prime-numbers - so don't divide by 9, 15. If it didn't divide by 3, it's not going to divide by 9. If it didn't divide by 5, it's not going to divide by 15. When numbers get a bit bigger, about 2 in 3 numbers are NOT primes.Code:int is_prime(int n)
{
if(n % 2 == 0) return 0;
for(i = 3; i *i < n; i++) {
if (n % i == 0) return 0;
}
return 1;
}
--
Mats
One thing you can do is keeping track of all prime numbers you find, and only testing against those. Repeated exact prime number testing is pretty much a trade-off between memory and speed.
>> The really naive approach is:
just for the sake of correctness, 1 is not a prime.
>> Repeated exact prime number testing is pretty much a trade-off between memory and speed.
which is why probabalistic and deterministic algorithms (such as Miller-Rabin and AKS) are more often used in practice, since they are efficient in both respects.
It says so in your code (and your code also says that 2 is not prime), but then again, your code snippet was just an example not intended to work out of the box.Quote:
I'm sorry, but where does it say that 1 is a prime in my text?
well, the function you posted would report it as being so. also, numbers less than 1 are not generally not tested for primality.
Ah yes, now I get it. Yeah, my code is a bit broken in all sorts of ways. It also don't work for primes under 9, since it never enters the loop in that case - I was trying to be clever and check for the square-root in a different way, but it breaks the for-loop before it's entered, since ( 3 * 3 > n) is not true.
And of course, it should check for exactly 2 and return 1.
--
Mats