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.

1 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 primesMemory 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