Primes

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Marcin Kwiatkowski
New poster
Posts: 5
Joined: Thu Jan 01, 2004 10:43 pm
Location: Gdynia, Poland

Primes

Post by Marcin Kwiatkowski »

Could anybody tell me if there's a method which checks if the number n is a prime? I know only an algo O(sqrt(n)) which is well-know. There's Eratostenes' Sieve too, but the big numbers cannot be checked due to memory limits.
"Imagination is more important than knowledge" Albert Einstein
Top
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

http://mathworld.wolfram.com/Rabin-Mill ... eTest.html
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.
Top
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Contact Larry

Post by Larry »

You can also check out the BigInteger source code in Java's API. They have various implementation in there.
Top
Post Reply

Return to “Algorithms”