Welcome, guest | Sign In | My Account | Store | Cart

Prime Number Generator Checker (Python recipe) by TheMachineCharmer
ActiveState Code (http://code.activestate.com/recipes/576543/)

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

Python, 32 lines
Download
 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
Tags: number_theory, primality_testing, prime_number

3 comments

David Lambert 15 years, 6 months ago  # | flag

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

TheMachineCharmer (author) 15 years, 6 months ago  # | flag

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

Holger Weisbrodt 14 years, 9 months ago  # | flag

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