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.

Last updated: 1997/06/05 23:52:16
URL: http://www.nmt.edu/~shipman/soft/clean/prime.html