March 26th, 2002 01:06 PM
Ah, The Sieve of Eratosthenes. I wrote some on it a while back if anyone is interested:
\"The purpose of abstraction is not to be vague, but to create a new semantic level in which one can be absolutely precise.\"
- Edsger Dijkstra
March 26th, 2002 01:17 PM
Rewandythal> also do b+2 instead of b++. If 2 is eleminated, then no even number can possible go into a.
garathjax> I don't remember exactly which test the ARP test is....and don't have time to look it up right now. I just wanted to warn you that certain tests only work for certain primes. Certain numbers (2^3-1 for example) follow set rules, but that doesnt mean that all primes follow the same rules. Some just make it quick to find. There is a project called the GIMP (I believe) which is working on determining extreamly large prime numbers. The last one was something like 4million digits. Their goal is to find the first prime number greater then 10million digits.
\"Ignorance is bliss....
but only for your enemy\"
March 26th, 2002 01:23 PM
b=2, b+2 takes is straight to 4, missing out 3, I'd have to go from b=1, which would return 1 and would *appear* therefore not to be prime (since a / 1 would be a whole number).
I could of course start at 3, but it'd then miss out the important /2 stage, so 4, for example, would be misreported as prime.
March 26th, 2002 01:30 PM
This solves the problem, by checking for divisible by 2 first, then starting at 3, incrementing in 2's (all the odd numbers).
int IsPrime(int a)
if( (a div 2) == (a / 2))
c = 1;
for(b = 3;b < sqrt(a); b + 2)
if( (a div b) == (a / b))
c = 1;
// Returns 0 if prime, 1 if not