Welcome, guest | Sign In | My Account | Store | Cart

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
 ``` 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.

Paul Miller 19 years ago

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.

Paul Miller 19 years ago

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

Paul Miller 19 years ago

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 ;-)

Paul Miller 19 years ago

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.

Paul Miller 19 years ago

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. ;)

Josiah Carlson 19 years ago

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

 Created by gian paolo ciceri on Thu, 21 Apr 2005 (PSF)

### Required Modules

• (none specified)