Since the excellent <a href="http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/366178">fast prime number list generator</a> recipe, it's simple to implement a function to check if its input it's a prime number.
Python, 11 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 | def isprime(aNumber):
'''return True if the number is prime, false otherwise'''
if aNumber < 2: return False
if aNumber == 2: return True
if (( aNumber / 2 ) * 2 == aNumber) :
return False
else:
klist = primes(int(math.sqrt(aNumber+1)))
for k in klist[1:]:
if (( aNumber / k ) * k == aNumber ): return False
return True
|
It complements the fast prime number list generator recipe.
Tags: algorithms
Highly inefficient. Try this with some large numbers (say 1000+ digits). For numbers of this magnitude, a probabilistic test such as Miller-Rabin is generally preferable. 30 rounds of Miller-Rabin can determine the primaility of any number with probability of error less than 1 in 10**18. I'd be willing to guess the probability of the computer having a random malfunction is higher.
Further note on memory consumption. This recipe involves the construction of the list of primes This recipe involves the construction of the list of primes
Memory consumption redux -- with correct formatting! This recipe involves the construction of the list of primes <= sqrt (aNumber). There are 50,847,534 prime numbers < 10 ** 9. Assuming 32 bits of storage for each, that would be nearly 194 megs of RAM simply to do a primality test on a 9 digit integer: clearly unacceptable.
inefficient, but not so memory hungry. Hi Paul, thanks for your feedback.
Yes the algorithm is slower than a direct trial-and-error, and substituting the prime list with calls to a sieve prime number generator, like the Recipe 117119, does not improve the situation: the result it's three time slower in my little experiments.
Only a remark about memory consumption: len(primes(int(math.sqrt(10**9+1)))) gives me 3401, it didn't take so much memory to handle such a list ;-)
Oops. Yeah, slight miscalculation. I forgot to take into account the sqrt operation. :P This recipe will take >194 megs to do a primality test on an 81 digit integer, not a 9 digit.
Dyslexia? Nah. :P. Make that 18 digit integer, not 81. :-) It seems I temporarily forgot the rules of exponentiation. (Not so good, since I am a grad student in math. ;)
You want Rabin-Miller? You got it! I got bored and posted a version of the Rabin-Miller test of primality that I wrote a few months back, it includes a "generate a prime number of b bits (with confidence parameter)" function.
Enjoy!
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/410681