Prime Number

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Prime Number

Post by _.B._ »

Greetings!
Which is the fastest way to find if a number is Prime?
My algorithm, brought from Pascal, is this:

[cpp]bool Prime(unsigned long n)
{ unsigned long Con = 1,Max = sqrt(n);
if (n < 2)
return false;
while ((Max > 1) && (Con < 2))
{ if (n % Max == 0)
Con++;
Max--;
}
return Con == 1;
}
[/cpp]
_.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

Depends on how big n is...

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Up to 10,000,000

Post by _.B._ »

Let's say the classical 1 to 1,000,000, or for 1 to 10,000,000.
No bigger than 10,000,000.
_.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek »

why mod by even things ? just check mod by 2 in the beginning then you can speed things up by a factor of 2.

[c]
int i;
if (n<2) return 0;
else if (!(n&1)) return n==2;
else {
for (i=3;i*i<=n;i+=2) if (!(n%i)) return 0;
return 1;
}

[/c]

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

Also depends on how many numbers you want to check of primeness.. if just a few, the simple check all numbers up to sqrt(n) is probably fastest..

If you need to do it a lot more times, then sieving up to 10,000,000 and using a O(1) lookup is probably faster..

If the numbers are even higher than that, then you'd need to look up some more general primality tests (which will determine strong probable primes [i.e. is prime with xx% certainty], and may still not be necessarily prime, depending on how the particular test works)..

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Thanks.

Post by _.B._ »

Thanks to both of you!
I'll consider it all :wink:

Keep posting!
_.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per »

IMO, the best algorithm is Miller-Rabin (though of course, it depends on application. If you need to check if every element from 1 to n is prime, you should use a sieve, but if n is at least, say, a few millions, and n is much larger than the number of queries, I would recommend Miller-Rabin).

http://www.google.com/search?q=miller-rabin

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Have to check it.

Post by _.B._ »

Greetings Per!
Thanks, I'll have to check for that too.

Keep posting!
_.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

If you want to see implementations, I recommend a look at Java's BigInteger class (the source).

Post Reply

Return to “Algorithms”