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