Creates a reference table of prime numbers, and some functions. More...

#include <Primes.h>

Static Public Member Functions
static Bool	isPrime (uInt number)
	This function takes number and returns "True" if number is prime, "False" if it is not.
static uInt	aLargerPrimeThan (uInt number)
	This function returns the closest integer larger than number from the table of primes.
static uInt	nextLargerPrimeThan (uInt number)
	This function finds the next largest prime than number, returns that value and stores it in the table of primes.
static uInt	smallestPrimeFactor (uInt number)
	This function returns the smallest factor of number.
static Block< uInt >	factor (uInt number)
	This function returns a block, of variable length, with each factor indexed.
static uInt	nCachedPrimes ()
	This function returns the number of primes stored in the primes table.
static void	initializeCache ()
	This function resets the table of prime numbers to contain 31 prime numbers to avoid consuming too much memory.
static Block< uInt >	cachedPrimes ()
	This function returns the table of prime numbers.
Static Private Attributes
static Block< uInt >	cacheTable
	This is the table which stores the prime numbers.

Detailed Description

Creates a reference table of prime numbers, and some functions.

Review Status

Reviewed By:: Gareth Hunt
Date Reviewed:: 94/08/19
Test programs:: tPrimes

Prerequisite

Understanding Block is only peripherally important.

Etymology

Prime has its usual definition (a number whose only factors are itself and one.) Zero and one are not considered to be prime.

Synopsis

The primary function of the Primes class is to create and maintain a list of prime numbers. This class has no constructors; all member functions are therefore declared static. The class maintains an internal cache table of prime numbers. There are also several member functions of more general use, which do not access the cached table.

The table is initialized to contain the next prime greater than each power of two. The function "aLargerPrimeThan" accepts a number and returns a larger prime number from the table of prime numbers. The function "nextLargerPrimeThan" finds the next greater integer that is a prime, returns it, and inserts it into the table. There are also functions to initialize and examine the table.

The basic prime number operations are done in three functions: "isPrime" determines whether a given number is a prime; "smallestPrimeFactor" finds the smallest factor of a given number; and "factor" returns a Block<uInt> containing a number's factors.

Example

    #include <scimath/Mathematics/Primes.h>
    #include <casa/Utilities/Assert.h>
    #include <iostream>
   
    // Refer also to tPrimes.cc
   
    int main() {
        Block<uInt> BB, DD;
        uInt C, i;
        if(! Primes::isPrime(4)) {                         //if this number 
            cout<<"Four is not a prime number"<<endl;      //is not prime
            BB = Primes::factor(4);                        //than factor it
   
            if( BB[0] != Primes::smallestPrimeFactor(4) ){ //check that first 
                                                           //factor equals
                 cerr<<"something is wrong"<<endl;         //the smallest 
            }
            cout<<"4 factored:"<<endl;
            for ( i = 0; i < BB.nelements(); i++ ) {
                cout<<BB[i]<<endl;
            }
   
            C = Primes::aLargerPrimeThan(4);  
            if ( (C-5) > 4 ) {                         //if difference is more 
                                                       //than five, then
                C = Primes::nextLargerPrimeThan(4);    //find next lprime
            } 
            DebugAssertExit( C == Primes::aLargerPrimeThan(4)); //now the prime resides
        }                                              //in the cache table 
        if( Primes::nCachedPrimes() > 50 ) {
            Primes::initializeCache();
        }
        DD = Primes::cachedPrimes();
        cout<<"The Table of Primes"<<endl;
        for ( i = 0; i < Primes::nCachedPrimes(); i++ ) {
            cout<<DD[i]<<endl;
        }
        return 0;
    }

Motivation

This class was conceived during the coding of a class that creates hash tables. The hash table class works best with a table whose size is prime. It uses the Primes class's function "nextLargerPrimeThan" to find a prime number that is close to an appropriate size. This prime number becomes the size of the hash table.

To Do

This class should not be used to generate large sets of prime numbers - it is not designed for efficiency at this. The algorithm checks 2, 3, and (6n +/- 1) up to the square root of the candidate prime.
The size of the prime numbers are restricted by the size of an unsigned integer (2^31-1 on 32 bit machines).

Definition at line 131 of file Primes.h.

Member Function Documentation

static uInt casa::Primes::aLargerPrimeThan ( uInt number ) [static]

This function returns the closest integer larger than number from the table of primes.

If there is no entry in the table of primes which is larger than number, a zero is returned.

static Block<uInt> casa::Primes::cachedPrimes ( ) [inline, static]

This function returns the table of prime numbers.

Definition at line 166 of file Primes.h.

References cacheTable.

static Block<uInt> casa::Primes::factor ( uInt number ) [static]

This function returns a block, of variable length, with each factor indexed.

For example, if number equaled 4, then the return block would have a length of two, and have a two stored in each cell. One and zero are special cases; this function returns a one-cell block which holds one or zero, respectively.

static void casa::Primes::initializeCache ( ) [static]

This function resets the table of prime numbers to contain 31 prime numbers to avoid consuming too much memory.

static Bool casa::Primes::isPrime ( uInt number ) [static]

This function takes number and returns "True" if number is prime, "False" if it is not.

static uInt casa::Primes::nCachedPrimes ( ) [inline, static]

This function returns the number of primes stored in the primes table.

Definition at line 158 of file Primes.h.

References cacheTable, and casa::Block< T >::nelements().

static uInt casa::Primes::nextLargerPrimeThan ( uInt number ) [static]

This function finds the next largest prime than number, returns that value and stores it in the table of primes.

static uInt casa::Primes::smallestPrimeFactor ( uInt number ) [static]

This function returns the smallest factor of number.

Member Data Documentation

Block<uInt> casa::Primes::cacheTable [static, private]

This is the table which stores the prime numbers.

Definition at line 172 of file Primes.h.

Referenced by cachedPrimes(), and nCachedPrimes().

The documentation for this class was generated from the following file:

casa/BasicMath/Primes.h

casa::Primes Class Reference [BasicMath_module]

Static Public Member Functions

Static Private Attributes