Wrapped In Python – Edition 2 – Prime Number Generator

Python Prime Number Generator

Perhaps just a step up from writing your first “Hello World” script.  I wrote [yet another] prime number generator.  I’m sure this can be done in a variety of ways but I used what I currently know to figure out how to determine if a number is prime.

Here’s the code:


#!/usr/bin/env python
print "2 is prime"
for i in range(3,1000000,2):
	num = range(2,i)
	counter = 0
	for each in num:
		if float(i % each) == 0.0:
			pass
		else:
			counter += 1
	if len(num) == counter:
		print "%d is prime." % i

The code will calculate up to 9,999,999 and tell you if the number is prime.  I have checked it randomly against the first 10,000 or so primes and it’s spot-on.  I’m not sure if this is how other people calculate primes but it was the first way I figured it out.  Give it a run on your system.  If nothing else it’s interesting to see your computer slow down in its determination of the next prime as the numbers it has to check get larger.

Note: In order to speed up the script I set the step to 2 (i.e.range(1, 1000000, 2)).  This allows me to skip checking even numbers for prime but also causes the number two (2) to be skipped and therefore not identified as a prime.  I cheated and added a simple print statement to keep 2 on the list.  If you remove the step (i.e. range(1,1000000)) the number two will be ID’d as prime but it doubles the computational effort (even numbers get checked, which is a waste of time).

Another note:  The step range(1,1000000,2) also includes all numbers that end in 5 (15, 25, 35, 525, etc.).  Five (5) is the only prime that ends with five so the script loses some efficiency because it is checking theses numbers, too.  I dabbled with some regular expressions to identify all numbers in the range(1,10000000,2) that end with 5 but nothing worked right away.  I’m sure it’s easy but I just haven’t figured out how to do it yet.  I’ll come back to it when I better learn how to do some pattern matching with python.

A simple modification of this script allows you to generate all of the primes in a range you specify.  For example, if you need to know all of the primes from 10,000 to 20,000, this will do it for you.

Here’s the Code:


#!/usr/bin/env python

print ""
print "*************************************************"
print "**          Prime Number Generator             **"
print "*************************************************"
print """This script will generate a list of prime numbers
within a range you specify.
"""
print ""
lower_range = int(raw_input("Enter the starting number: "))
upper_range = int(raw_input("Enter the upper range: "))
for i in range(lower_range,upper_range):
	num = range(2,i)
	counter = 0.0
	for each in num:
		if float(i % each) == 0.0:
			pass
		else:
			# if the modulus is not zero, increase the counter by 1.
			counter += 1
	if len(num) == counter:
		# if the total number of non-zero modulus' is equal to the 
		# number of numbers in the range of i-2, the number is prime.
		# In other words, every number in the range has a non-zero
		# modulus (i.e it's prime)
		print "%i is prime." % i

Cheers,

Colin Weaver

Previous Post:  Wrapped In Python – Edition 1
Next Post: Wrapped In Python – Edition 2 – Prime Number Verifier

If you liked this post, please consider sharing it.  Thanks!

About the Author

Colin Weaver

Colin Weaver is co-owner and lead instructor at ITdojo, Inc., a network security and information assurance training center and consulting firm located in Virginia Beach, VA. His passion for technology, networks, and security has led him to become enthralled with the idea of IPv6 and its implementation. In this blog he will share with you glimpses of what he has learned and a hint at what you’ll learn in his classes.