## Saturday, 31 January 2009

### 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
```