Python RSS Python RSS

Check if a number is a prime number (Python)

Please support our Python advertiser: Programming Forums - DaniWeb Sister Site
vegaseat vegaseat is offline Offline Mar 3rd, 2007, 2:05 pm |
0
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.
Show Printable Version Show Printable Version
Quick reply to this message  
Code Snippet
•
•
•
•
Python Syntax
Toggle Plain Text
  1. # prime numbers are only divisible by unity and themselves
  2. # (1 is not considered a prime number by convention)
  3.  
  4. def isprime(n):
  5.     '''check if integer n is a prime'''
  6.     # make sure n is a positive integer
  7.     n = abs(int(n))
  8.     # 0 and 1 are not primes
  9.     if n < 2:
  10.         return False
  11.     # 2 is the only even prime number
  12.     if n == 2: 
  13.         return True    
  14.     # all other even numbers are not primes
  15.     if not n & 1: 
  16.         return False
  17.     # range starts with 3 and only needs to go up the squareroot of n
  18.     # for all odd numbers
  19.     for x in range(3, int(n**0.5)+1, 2):
  20.         if n % x == 0:
  21.             return False
  22.     return True
  23.  
  24. # test ...
  25. print isprime(1)       # False
  26. print isprime(2)       # True
  27. print isprime(3)       # True
  28. print isprime(29)      # True
  29. print isprime(345)     # False
  30. print isprime(999979)  # True
  31. print isprime(999981)  # False
Code Snippet Comments
0
vegaseat vegaseat is offline Offline | Apr 28th, 2007
•
•
•
•
Filtered out even numbers, except number 2, to speed things up.
 
0
theApprentice() theApprentice() is offline Offline | Sep 19th, 2007
•
•
•
•
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?
 
0
Toster Toster is offline Offline | Jun 3rd, 2008
•
•
•
•
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

python Syntax (Toggle Plain Text) 
  1. def isprime(n):
  2.     if n == 2:
  3.         return 1
  4.     if n % 2 == 0:
  5.         return 0
  6.  
  7.     max = n**0.5+1
  8.     i = 3
  9.  
  10.     while i <= max:
  11.         if n % i == 0:
  12.             return 0
  13.         i+=2
  14.  
  15.     return 1
 
0
slate slate is offline Offline | Jun 7th, 2008
•
•
•
•
Simple RSA primtest. Does not work on universal pseudo primes.

python Syntax (Toggle Plain Text) 
  1. def isprime(n,PROB):
  2.     '''returns if the number is prime. Failure rate: 1/4**PROB '''
  3.     if n==2: return '1'
  4.     if n==1 or n&1==0:return '0'
  5.     s=0
  6.     d=n-1
  7.     while 1&d==0:
  8.         s+=1
  9.         d>>=1
  10.     for i in range(PROB):
  11.         a=random.randint(2,n-1)
  12.         composit=True
  13.         if pow(a,d,n)==1:
  14.             composit=False
  15.         if composit:
  16.             for r in xrange(0,s):
  17.                 if pow(a,d*2**r,n)==n-1:
  18.                     composit=False
  19.                     break
  20.         if composit: return False
  21.     return True
 
 

Quick Comment
•
•
•
•
•
•
•
•
Message:
•
•
•
•


Similar Threads
Thread Tools Search this Thread



abrupt ansi anti approximation assignment avogadro backend beginner binary bluetooth calculator character cmd code customdialog decimals dictionaries dictionary directory drive dynamic error examples excel exe file float format function gnu graphics gui heads homework http ideas import input java launcher leftmouse line linux list lists logging loop module mouse number numbers output parsing path pointer port prime programming progressbar projects push py2exe pygame pyqt python random recursion schedule scrolledtext sqlite statistics stdout string strings sudokusolver sum table terminal text thread threading time tkinter tlapse tricks tuple tutorial twoup ubuntu unicode update urllib urllib2 variable ventrilo wikipedia windows write wxpython xlib
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC