Rodney Dunning's Home Page | Research and Scholarship | VPython | Finding Prime Numbers
Introduction
Any number evenly divisible only by itself and one is called prime. Two is the smallest and only even prime number. The next ten prime numbers after two are 3, 5, 7, 11, 13, 17, 19, 23, 29, and 31. The prime numbers have been a source of much inspiration in number theory. There are many important and thus far unproved assertions regarding the prime numbers. For example, Euler, working from an assertion made by Goldbach, asserted that even number greater than two is the sum of two prime numbers.
Description
This program doesn't prove any famous conjectures! But it will find all the prime numbers between 2 and a user-supplied upper limit. The program works by a well-known brute force method, so it isn't very fast. Be prepared for a long wait if you want to find all the prime numbers between 2 and 100,000.
When you execute the program, you will be prompted for the upper limit. The program will return all the prime numbers between 2 and the upper limit, inclusive.
Screen Shot
There is no visual component to this program. But here is a sample output stream, for which the user requested all the prime numbers between 2 and 200:
>>> ================================ RESTART ================================ >>> This program finds all the prime numbers between 2 and an upper limit that you provide. It works by brute force, so it's not very fast. Enter the upper limit: 200 Your upper limit is 200 ------------------------------------- There are 46 prime numbers between 2 and 200 ------------------------------------- No. | Prime 1 | 2 2 | 3 3 | 5 4 | 7 5 | 11 6 | 13 7 | 17 8 | 19 9 | 23 10 | 29 11 | 31 12 | 37 13 | 41 14 | 43 15 | 47 16 | 53 17 | 59 18 | 61 19 | 67 20 | 71 21 | 73 22 | 79 23 | 83 24 | 89 25 | 97 Hit enter to continue 26 | 101 27 | 103 28 | 107 29 | 109 30 | 113 31 | 127 32 | 131 33 | 137 34 | 139 35 | 149 36 | 151 37 | 157 38 | 163 39 | 167 40 | 173 41 | 179 42 | 181 43 | 191 44 | 193 45 | 197 46 | 199 -------------------------------------
Suggested Use
I haven't used this program in any courses. You can show it to students as an example program to teach programming skills. Some suggestions for programming projects:
- Investigate the speed of algorithm. Are there any ways to speed it up?
- Research alternative algorithms for generating prime numbers, perhaps even ones known to fail after a certain threshold, or ones known to skip some primes. Code these and compare them to the brute-force method.
- Alter the code to allow the user to request the first n primes, instead of the current version which asks the user for an upper limit on the check-range.
- The code is fast enough for demonstation purposes when the upper-limit is 10,000 or less.
- On my University-issued desktop machine, the program finds all the primes between 2 and 10,000 in less than 1 second. It takes about 25 seconds to find all the primes between 2 and 100,000.
Source Code
The source code appears between the bars below. Copy and paste the code into the Python IDLE environment, and hit F5 to run the code.
from __future__ import division
from math import *
"""
Rodney Dunning
Assistant Professor of Physics
Longwood University
"""
#-----------------
#
# print_intro
#
#-----------------
def print_intro():
print "This program finds all the prime numbers"
print "between 2 and an upper limit that you provide."
print "It works by brute force, so it's not very fast."
print "" # spacer
#-----------------
#
# get_upper_limit
#
#-----------------
def get_upper_limit():
upper_limit = input("Enter the upper limit: ")
print "" # spacer
print "Your upper limit is ",upper_limit
print "" # spacer
return upper_limit
#-------------------
#
# print_prime(x)
#
#-------------------
def print_primes(prime_list,upper_limit):
print "\n" #spacer
print "-------------------------------------"
print " There are %1i prime numbers between" %len(prime_list)
print " 2 and %1i" %upper_limit
print "-------------------------------------\n"
print " No. | Prime"
print "\n" #spacer
for i in range(1,len(prime_list)+1):
print "%4i | %6i" %(i,prime_list[i-1])
if i%25 == 0: raw_input("Hit enter to continue")
print "-------------------------------------\n"
#-------------------
#
# find_primes
#
#-------------------
def find_primes(upper_limit):
prime_list = [] # a list of primes found so far
prime_list.append(2) # 2 is prime!!!
prime_list.append(3) # 3 is prime!!!
prime_list.append(5) # 5 is prime!!!
# All the multiples of 2 and 3 are not prime
# so there is no point in checking them.
num_primes = 3 # we start with three primes
candidate = 7 # our first candidate
increment = 4
while(candidate <= upper_limit):
x = 0 # array index for prime_list
prime = 1 # logical flag
## print "candidate is ",candidate
while(x < (num_primes-1) and prime):
trial_divisor = prime_list[x] # start with five
## print "trial_divisor= ",trial_divisor
## print "candidate % trial_divisor= ",candidate%trial_divisor
if(candidate%trial_divisor == 0):
## print candidate, " is NOT PRIME."
prime = 0
x+=1
if(prime):
prime_list.append(candidate)
num_primes += 1
#print_prime(candidate)
candidate += increment
if(increment ==4):
increment = 2
else:
increment = 2
return prime_list
#-------------------
#
# main (program)
#
#--------------------
def main():
print_intro()
upper_limit = get_upper_limit()
prime_list = find_primes(upper_limit)
print_primes(prime_list,upper_limit)
main()