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

**See also:** Example programs written in Cleanroom style

**Previous:** My Cleanroom naming conventions

Site map

John W. Shipman,
`john@nmt.edu`
##### Last updated: 1997/06/05 23:52:16

URL: http://www.nmt.edu/~shipman/soft/clean/prime.html