I need a function that returns True or False if an integer n is a prime. Any 'high speed' thoughts?
sneekula, I don't want to sound rude, but your one-sentence-question-posts are annoying. Why don't you try to find the answer alone first? If you're stuck, post what you have tried and we will try to help you.
BTW: The internet is full of isprime functions in any language you can dream of. 2 minutes of googling, that's all you need to do ;)
Forget the googlling, doing a search for "prime" within our code snippets section landed a function that outputs a list of prime numbers in python :)
Forget the googlling,
You are absolutely right, a search should always start in our snippets section :) But, searching for prime python via Google, I found a link to a snippet here (on the second page). You see, Google is not that bad :)
Our snippet examples give you a list of primes. You could get a list of primes in the range of your numbers, and then see if your numbers are in it. For simplicity sake you can use this small function ...
# prime numbers are only divisible by unity and themselves # (1 is not considered a prime number) def isprime(n): '''check if integer n is a prime''' # range starts with 2 and only needs to go up the squareroot of n for x in range(2, int(n**0.5)+1): if n % x == 0: return False return True # test ... print isprime(29) # True print isprime(345) # False print isprime(8951) # True
If you're looking to test really large numbers, here's an implementation of the Rabin-Miller probabilistic test:
def primes(n): """ primes(n) --> primes Return list of primes from 2 up to but not including n. Uses Sieve of Erasth. """ if n < 2: return  nums = range(2,int(n)) p =  while nums: new_prime = nums p.append(new_prime) for i in nums[1:]: if i % new_prime == 0: nums.remove(i) nums.remove(nums) return p def power_mod(a, b, n): """ power_mod(a,b,n) --> int Return (a ** b) % n """ if b < 0: return 0 elif b == 0: return 1 elif b % 2 == 0: return power_mod(a*a, b/2, n) % n else: return (a * power_mod(a,b-1,n)) % n def rabin_miller(n, tries = 7): """ rabin_miller(n, tries) --> Bool Return True if n passes Rabin-Miller strong pseudo-prime test on the given number of tries, which indicates that n has < 4**(-tries) chance of being composite; return False otherwise. http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html """ if n == 2: return True if n % 2 == 0 or n < 2: return False p = primes(tries**2) # necessary because of the test below if n in p: return True s = n - 1 r = 0 while s % 2 == 0: r = r+1 s = s/2 for i in range(tries): a = p[i] if power_mod(a,s,n) == 1: continue else: for j in range(0,r): if power_mod(a,(2**j)*s, n) == n - 1: break else: return False continue return True
I can't guarantee that the implementation is correct, although it has passed testing so far. Also, the RM test only gives a probability of primeness, not absolute certainty. However, with default settings one has a 0% chance of false positives and a 0.006% chance of a false negative.
1 is not prime:
def isPrime(n): if n == 1: return 0 else: for x in range(2,int(n**0.5)+1): if n%x == 0: return 0 return 1
Here is a shorter primeList:
primeList = lambda n: set([i for i in range(2,n)]) ^ set([i for i in range(2,n) for x in range(2,int(i**0.5)+1) if i%x == 0])