ActiveState Code

Recipe 410662: A function to check if a number is prime

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

Discussion

It complements the fast prime number list generator recipe.

Comments

  1. 1. At 9:10 p.m. on 21 apr 2005, Paul Miller said:

    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.

  2. 2. At 1:05 a.m. on 23 apr 2005, Paul Miller said:

    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

  3. 3. At 1:19 a.m. on 23 apr 2005, Paul Miller said:

    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.

  4. 4. At 9:10 a.m. on 23 apr 2005, gian paolo ciceri (the author) said:

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

  5. 5. At 12:46 p.m. on 23 apr 2005, Paul Miller said:

    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.

  6. 6. At 9:19 p.m. on 23 apr 2005, Paul Miller said:

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

  7. 7. At 5:56 p.m. on 24 apr 2005, Josiah Carlson said:

    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

Sign in to comment