Calculating Prime Numbers using python
This blog article shows a python exercise which consists on calculating some prime numbers using trial division algorithm.
You can copy this code in a script file and then execute it!
#!/usr/bin/env python
#Prime numbers
import sys
import math
print "Prime numbers"
#Asks user how many numbers he wants to calculate.
top = int(raw_input("How many prime numbers do you want to calculate?: "))
if (top <1 ) :
print "Error: Invalid number. It must be greater than one"
sys.exit
#Initializing some variables
a = 3 # first number to test if it is prime.
result = [2] # result list begins with prime number 2.
num = 1 # number of already calculated primes.
print 2,
while num < top : # main loop
cont = 0
# Performs the division test
while 1 :
divisor = result[cont] # we only test with already calculated prime numbers.
(quotient, remainder) = divmod(a,divisor) # calculates quotient and remainder at the same time.
if (remainder) :
if divisor <= quotient :
cont += 1
else:
result.append(a)
print a, # number a is a prime.
num += 1
break
else:
break # number a is not a prime
a += 1 # calculate next number to test.
This other script avoids testing numbers that are multiple of 2,3,5 or 7. Also calculates the integer square root to obtain the higher divisor limit to test for each number.
#!/usr/bin/env python
#Prime numbers
import sys
import math
print "Prime numbers"
#Asks user how many numbers he wants to calculate.
top = int(raw_input("How many prime numbers do you want to calculate?: "))
if (top <1 ) :
print "Error: Invalid number. It must be greater than one"
sys.exit
#Initializing some variables
a = 11 # first number to test if it is prime
statea = 0
stateb = 0
result = [7] # result list begins with prime number 7
num = 4 # number of already calculated primes.
print 2, 3, 5, 7,
while num < top : # main loop
cont = 0
#Calculates the integer square root of a
low = 1
upper = a
while (upper - low) > 1 :
med = (low + upper)/2
temp = med * med
if temp > a :
upper = med
else:
low = med
if temp == a :
break
# Performs the division test
while 1 :
divisor = result[cont]
if (a % divisor) :
if divisor <= low :
cont += 1
else:
result.append(a)
print a, # number a is a prime
num += 1
break
else:
break # number a is not a prime
# Calculates next number to test if it is a prime.
if (stateb == 4) or (stateb == 6) :
a += 6
stateb += 1
elif statea :
a += 4
statea = 0
if stateb == 7 :
stateb = 0
else :
stateb += 1
else :
a += 2
statea = 1
stateb +=1
