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 18 years, 10 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 18 years, 10 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 18 years, 10 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) 18 years, 10 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 18 years, 10 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 18 years, 10 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 18 years, 10 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