Next / Previous / Shipman's Home Sweet Homepage / Site map

## Cleanroom examples: Prime number testing

This is a small object illustrating numerical programming in the Python language. Module prime.py defines a class Prime. The purpose of a Prime object is to work with prime numbers---to test numbers for primality, and to find the set of prime factors in a given number.

We could just provide simple functions for primality testing and factoring. However, the process of testing a number for primes involves generating primes. For efficiency's sake, we provide an object that remembers all the primes it has already generated, rather than discarding them.

• To create a Prime object, use this Python function:
`    p = Prime()`
where p is the name of the variable to which you want to assign the Prime object. You will need to do this only once when your program starts up.
• To test a positive number n to see if it is prime, use a statement something like this:
`    f = p.factor(n)`
where p is a Prime object. This method returns the smallest prime factor of n other than 1 (except that the value 1 will be returned for n=1). If n is prime, this method returns None.
• To obtain all the prime factors (other than 1) of a number n, use this method:
`    L = p.factorize(n)`
The value returned is a list containing the prime factors of n in ascending order. The value 1 will not be included unless n is 1. If n is prime, the returned value will be a one-element list [n].
• See the Python source code for this object. Of particular interest is the mutual recursion between the .factor() and ._fill methods. Proving termination of this recursion was not difficult, but it is up to the author to notice the recursion and point it out to the verification panel.

Next: Cleanroom examples: skiplist.py, a container class