This simple isprime(number) function checks if the given integer number is a prime number and returns True or False. The function makes sure that the number is a positive integer, and that 1 is not considered a prime number.
To find out if an integer n is odd one can use n & 1, to check for even one can then use not n & 1 or the more traditional n % 2 == 0 which is about 30% slower.
# prime numbers are only divisible by unity and themselves
# (1 is not considered a prime number by convention)
def isprime(n):
'''check if integer n is a prime'''
# make sure n is a positive integer
n = abs(int(n))
# 0 and 1 are not primes
if n < 2:
return False
# 2 is the only even prime number
if n == 2:
return True
# all other even numbers are not primes
if not n & 1:
return False
# range starts with 3 and only needs to go up the squareroot of n
# for all odd numbers
for x in range(3, int(n**0.5)+1, 2):
if n % x == 0:
return False
return True
# test ...
print isprime(1) # False
print isprime(2) # True
print isprime(3) # True
print isprime(29) # True
print isprime(345) # False
print isprime(999979) # True
print isprime(999981) # False
# extra test ...
print isprime(49) # False
print isprime(95) # False
Filtered out even numbers, except number 2, to speed things up.
Hi,
The code listed above does not seem accurate as numbers like 49 and 95 pass the test and yet they are not prime numbers!
Perhaps a flaw in the algorithm used?
Editor's note: as you can see, 49 and 95 do not pass the test, not sure what's wrong with you?
I think the mistake is that you converted the square root to an int, because the code I wrote a couple of years ago works fine, and its almost the same
def isprime(n):
if n == 2:
return 1
if n % 2 == 0:
return 0
max = n**0.5+1
i = 3
while i <= max:
if n % i == 0:
return 0
i+=2
return 1
Editors note: the range function in vegaseat's code needs integers, so it's correct.
Simple RSA primtest. Does not work on universal pseudo primes.
def isprime(n,PROB):
'''returns if the number is prime. Failure rate: 1/4**PROB '''
if n==2: return '1'
if n==1 or n&1==0:return '0'
s=0
d=n-1
while 1&d==0:
s+=1
d>>=1
for i in range(PROB):
a=random.randint(2,n-1)
composit=True
if pow(a,d,n)==1:
composit=False
if composit:
for r in xrange(0,s):
if pow(a,d*2**r,n)==n-1:
composit=False
break
if composit: return False
return Truedaniweb is very useful to beginners to learn IT.i hope i would learn more from u...........bye
this works fine returning true if prime and false with the smallest number that divides it if it is false.
def isprime(x):
x = abs(int(x))
if x < 2:
return "Less 2", False
elif x == 2:
return True
elif x % 2 == 0:
return False
else:
for n in range(3, int(x**0.5)+2, 2):
if x % n == 0:
return n, False
return TruePardon my previous post. The indentation was not right.This one works fine.
for n in range(2,10):
for x in range(2,n):
if n%x == 0:
print n,'equal',x,'*',n/x
break
else:
print n,'is a prime number'
Hey thank you for this epic post!!! I used it as a base for checking if a number was prime in an algorithm I made for Project Euler #3.
Thanks again!!!!
how avout this one?:
def is_prime(n):
i = 2
if n < 2:
return False
while i < n:
if n % i == 0:
return False
else:
i += 1
return True
Editor's note: too slow for large n
gmorcan,
using Python module timeit and a rather small prime number like 999979, your function is 2700 times slower than vegaseat's function.
OK, here is a really optimized version for this classic problem. This is not originally mine (but have done very similar).
It utilizes the fact that primes > 4 are 1(mod 6) or 5(mod 6). Actually I editted it a lot now before posting to be more according to format standards of PEP8.
def is_prime(n):
if n == 2 or n == 3:
return True
elif n < 2 or n % 2 == 0:
return False
elif n < 9:
return True
elif n % 3 == 0:
return False
r = int(sqrt(n))
f = 5
while f <= r:
if n % f == 0 or n % (f + 2) == 0:
return False
else:
f += 6
return True
How do you feel witth this?
import re
def is_prime(num): return not re.match(r"^1?$|^(11+?)\1+$", "1" * num)
def pri(num): return is_prime(num)
Real hack, and surely stupendously inefficient. Best as joke or concept. Do not try to test (2**13-1) with it.
Super fast for very large numbers:
def miller_rabin_isprime(a, i, n):
"""
Miller-Rabin primality test
returns a 1 if n is a prime
usually i = n - 1
does not test prime 2
"""
if i == 0:
return 1
x = miller_rabin_isprime(a, i // 2, n)
if x == 0:
return 0
y = (x * x) % n
if ((y == 1) and (x != 1) and (x != (n - 1))):
return 0
if (i % 2) != 0:
y = (a * y) % n
return y
i = 0
while(i <100):
j = 2
while (j<=(i/j)):
if not (i%j):break
j=j+1
if (j > i/j):print i ," is prime number"
i = i+1
Editor's note:
Let's say you want to know if 999979 is a prime number. How long would that take?
You have made the classic mistake of including even numbers = testing twice as many numbers. Start out with i=3 and add two on each pass.
I just got an automated email from Daniweb suggesting that I read this thread based on my recent activity. The code posts in this thread are fine, but most of the comment posts are curmudgeonly, rude, standoffish, exclusivist, and socially inept. People seem to think it's a violation of some natural law if a beginner programmer joins a discussion and tries to make a positive contribution by posting code. I'll definitely be putting some of you on my ignore list.
People seem to think it's a violation of some natural law if a beginner programmer joins a discussion and tries to make a positive contribution by posting code.
On the contrary, we answer beginner programmer's questions every day in the python forum and try to help them as much as we can. Correct errors and inefficiencies in code is not rude or socially inept: we all learn by our own mistakes.
I would advise beginner programmers to start their own thread with well described issues to solve. They will probably get better answers than by adding to a code snippet thread.
They may also find many ideas in Vegaseat's thread projects-for-the-beginner.
Hi, Grib,
Thanks for the link to that thread. I'll definitely be checking it out. What I'm really hungry for is some real-world problems to try to provide solutions for, but I realize it might be a bit too early for me to do that. Doing those kinds of projects could be a good alternative.
If there are similar threads available for html and javascript, I'd love to see links for them as well.
Eyetee
I don't understand what's going on with line 15 in vegaseat's code. What does not n & 1 do?
What does not n & 1 do?
& is the integer bitwise and operator. When n is an integer, n & 1 is the value of its first bit in base 2. Therefore, n & 1 has value 0 if n is even and 1 if n is odd. not n & 1 has the same meaning as n is even (which is less cryptic but is not python). Another way to say it is n % 2 == 0, but vegaseat thinks he gains some speed.
For a somewhat updated isprime function see:
http://www.daniweb.com/software-development/python/code/462120/isprime-function-python
Found this... thought it might be of help to folks here - the main module is pretty well commented, with lots of links to references:
`
def is_prime(x):
prime = False
if x > 1:
for i in range(2, x+1):
if x % i == 0 and i != x:
prime = False
break
else:
prime = True
return prime
`
Simpler than above examples, and creates a list of primes (to 10,000 in this example). Also, you only have to test x up to a half of n, as anything over a half of the number is not worth testing. (not worth testing if 17 can be dividied by 9, 10, 11, 12 etc.!) Also only tests odd numbers with the range (1,n,2):
primes = []
for n in range(1,10000,2):
for x in range(2,n/2):
if n%x == 0:
break
else:
primes.append(n)
print primes
@Gu1tar1st: As the square root of 17 is 4.123 you don't even have to test for divisibility from 5,6,7,8,9....
what does "not n & 1" do specifically?
Does it return False for all the even numbers above 2?
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.