ActiveState Code

Recipe 576543: Prime Number Generator Checker

This program implements primality testing function. The function is then used to generate prime numbers in the given range.

Python 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#
# prime number generator
# This program gets two number as input
# and prints
#       Prime numbers in the range
#       Actual number of primes in the range
#   and Estimation based on formula
#                     n
#           pi(n)= -------
#                   log(n)
#           pi(n)=number of primes less than n
#

from math import *
def isPrime(n):
    if n%2==0 and n!=2:return False    #if number is EVEN AND it is NOT 2

    k = n**0.5 ;  m = ceil(k)          #if number is PERFECT SQUARE
    if k==m:return False
    
    for i in xrange(3,int(m),2):       #divisibility test ODDS ONLY
        if n%i==0:return False
        
    return True                        #otherwise it is PRIME

if __name__=='__main__':
    s = input('Enter Start: ')
    e = input('Enter End:   ')
    s|=1                               #if s%2==0:s+=1   # ODDS only
    list = [x for x in range(s,e,2) if isPrime(x)] 
    print list,'\n',len(list),'\n',int(ceil(e/log(e)-s/log(s)))
    #prints list of primes , length of list , estimate using the formula

Comments

  1. 1. At 4:20 p.m. on 27 oct 2008, David Lambert said:

    I'd replace "if s%2==0:s+=1" with "s |= 1".

  2. 2. At 5:22 a.m. on 28 oct 2008, pratik deoghare (the author) said:

    Thanks David. REPLACED "if s%2==0:s+=1" with "s |= 1". More suggestions are welcome.

  3. 3. At 11:31 a.m. on 5 aug 2009, Holger Weisbrodt said:

    I'd check for e and s not equal 1 otherwise the formula will throw an exception (division by zero).

Sign in to comment