1,105,312 Community Members

Check if a number is a prime number (Python)

Member Avatar
Reputation Points: 1,544 [?]
Q&As Helped to Solve: 1,872 [?]
Skill Endorsements: 67 [?]
 
2
 

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.

# 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
Member Avatar
vegaseat
DaniWeb's Hypocrite
6,984 posts since Oct 2004
Reputation Points: 1,544 [?]
Q&As Helped to Solve: 1,872 [?]
Skill Endorsements: 67 [?]
Moderator
 
0
 

Filtered out even numbers, except number 2, to speed things up.

Member Avatar
theApprentice()
Newbie Poster
1 post since Sep 2007
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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?

Member Avatar
Toster
Newbie Poster
1 post since Jun 2008
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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.

Member Avatar
slate
Posting Whiz
375 posts since Jun 2008
Reputation Points: 163 [?]
Q&As Helped to Solve: 106 [?]
Skill Endorsements: 10 [?]
 
0
 

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 True
Member Avatar
coolkirankumar
Newbie Poster
1 post since Mar 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

daniweb is very useful to beginners to learn IT.i hope i would learn more from u...........bye

Member Avatar
kungfujam
Newbie Poster
7 posts since Jan 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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 True
Member Avatar
arindam31
Light Poster
48 posts since Mar 2011
Reputation Points: -8 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Pardon 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'
Attachments prime.txt (0.17KB)
Member Avatar
Gribouillis
Posting Maven
3,453 posts since Jul 2008
Reputation Points: 1,140 [?]
Q&As Helped to Solve: 883 [?]
Skill Endorsements: 18 [?]
Moderator
 
1
 
Member Avatar
zjtpjs4
Newbie Poster
13 posts since Jun 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 1 [?]
Skill Endorsements: 0 [?]
 
1
 

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

Member Avatar
gmorcan
Newbie Poster
5 posts since Apr 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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

Member Avatar
Lardmeister
Posting Virtuoso
1,966 posts since Mar 2007
Reputation Points: 434 [?]
Q&As Helped to Solve: 111 [?]
Skill Endorsements: 8 [?]
 
0
 

gmorcan,
using Python module timeit and a rather small prime number like 999979, your function is 2700 times slower than vegaseat's function.

Member Avatar
pyTony
pyMod
6,103 posts since Apr 2010
Reputation Points: 818 [?]
Q&As Helped to Solve: 1,056 [?]
Skill Endorsements: 42 [?]
Moderator
Featured
 
0
 

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
Member Avatar
filtre
Newbie Poster
1 post since May 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

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)
Member Avatar
pyTony
pyMod
6,103 posts since Apr 2010
Reputation Points: 818 [?]
Q&As Helped to Solve: 1,056 [?]
Skill Endorsements: 42 [?]
Moderator
Featured
 
0
 

Real hack, and surely stupendously inefficient. Best as joke or concept. Do not try to test (2**13-1) with it.

Member Avatar
HiHe
Posting Whiz
384 posts since Oct 2008
Reputation Points: 160 [?]
Q&As Helped to Solve: 54 [?]
Skill Endorsements: 6 [?]
 
0
 

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
Member Avatar
Bikash1990
Newbie Poster
1 post since Dec 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 
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?

Member Avatar
woooee
Posting Maven
2,796 posts since Dec 2006
Reputation Points: 783 [?]
Q&As Helped to Solve: 836 [?]
Skill Endorsements: 12 [?]
 
0
 

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.

Member Avatar
Eyeteeorg
Newbie Poster
21 posts since Dec 2012
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
-2
 

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.

Member Avatar
Gribouillis
Posting Maven
3,453 posts since Jul 2008
Reputation Points: 1,140 [?]
Q&As Helped to Solve: 883 [?]
Skill Endorsements: 18 [?]
Moderator
 
0
 

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.

You
Post:
Start New Discussion
Tags Related to this Article