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
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.
This function finds the next largest prime than number, returns that
value and stores it in the table of primes.
This function returns the smallest factor of number.
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.
This function returns the number of primes stored in the primes table.
This function resets the table of prime numbers to contain 31 prime
numbers to avoid consuming too much memory.
This function returns the table of prime numbers.
Example
#include <aips/Mathematics/Primes.h>
#include <aips/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
A List of bugs, limitations, extensions or planned refinements.
Member Description
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)
static uInt nextLargerPrimeThan(uInt number)
static uInt smallestPrimeFactor(uInt number)
adds to cache
static Block<uInt> factor(uInt number)
static uInt nCachedPrimes()
static void initializeCache()
static Block<uInt> cachedPrimes()