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.

7 comments

Paul Miller 16 years, 9 months ago  # | flag

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 16 years, 9 months ago  # | flag

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 16 years, 9 months ago  # | flag

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.

gian paolo ciceri (author) 16 years, 9 months ago  # | flag

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 16 years, 9 months ago  # | flag

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 16 years, 9 months ago  # | flag

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 16 years, 9 months ago  # | flag

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)
Python recipes (4591)
gian paolo ciceri's recipes (7)

Required Modules

  • (none specified)

Other Information and Tasks