casacore
Primes.h
Go to the documentation of this file.
1 //# Primes.h: This class provides some prime number operations using a cached table
2 //# Copyright (C) 1994,1995,1999,2001
3 //# Associated Universities, Inc. Washington DC, USA.
4 //#
5 //# This library is free software; you can redistribute it and/or modify it
6 //# under the terms of the GNU Library General Public License as published by
7 //# the Free Software Foundation; either version 2 of the License, or (at your
8 //# option) any later version.
9 //#
10 //# This library is distributed in the hope that it will be useful, but WITHOUT
11 //# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 //# FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
13 //# License for more details.
14 //#
15 //# You should have received a copy of the GNU Library General Public License
16 //# along with this library; if not, write to the Free Software Foundation,
17 //# Inc., 675 Massachusetts Ave, Cambridge, MA 02139, USA.
18 //#
19 //# Correspondence concerning AIPS++ should be addressed as follows:
20 //# Internet email: aips2-request@nrao.edu.
21 //# Postal address: AIPS++ Project Office
22 //# National Radio Astronomy Observatory
23 //# 520 Edgemont Road
24 //# Charlottesville, VA 22903-2475 USA
25 
26 //# $Id$
27 
28 #ifndef SCIMATH_PRIMES_H
29 #define SCIMATH_PRIMES_H
30 
31 #include <casacore/casa/aips.h>
32 #include <casacore/casa/Containers/Block.h>
33 #include <casacore/casa/OS/Mutex.h>
34 
35 namespace casacore { //# NAMESPACE CASACORE - BEGIN
36 
37 // <summary> Creates a reference table of prime numbers, and some functions </summary>
38 //
39 // <reviewed reviewer="Gareth Hunt" date="94/08/19" tests="tPrimes">
40 //
41 // <prerequisite>
42 // <li>Understanding Block is only peripherally important.
43 // </prerequisite>
44 //
45 // <etymology>
46 // Prime has its usual definition (a number whose only factors are
47 // itself and one.) Zero and one are not considered to be prime.
48 // </etymology>
49 //
50 // <synopsis>
51 // The primary function of the Primes class is to create and maintain a list of
52 // prime numbers. This class has no constructors; all member functions are
53 // therefore declared static. The class maintains an internal cache table of
54 // prime numbers. There are also several member functions of more general use,
55 // which do not access the cached table.
56 //
57 // The table is initialized to contain the next prime greater than each power
58 // of two. The function "aLargerPrimeThan" accepts a number and returns a
59 // larger prime number from the table of prime numbers. The function
60 // "nextLargerPrimeThan" finds the next greater integer that is a prime,
61 // returns it, and inserts it into the table. There are also functions to
62 // initialize and examine the table.
63 //
64 // The basic prime number operations are done in three functions: "isPrime"
65 // determines whether a given number is a prime; "smallestPrimeFactor" finds
66 // the smallest factor of a given number; and "factor" returns a Block<uInt>
67 // containing a number's factors.
68 // </synopsis>
69 //
70 // <example>
71 // <srcblock>
72 // #include <casacore/scimath/Mathematics/Primes.h>
73 // #include <casacore/casa/Utilities/Assert.h>
74 // #include <iostream>
75 //
76 // // Refer also to tPrimes.cc
77 //
78 // int main() {
79 // Block<uInt> BB, DD;
80 // uInt C, i;
81 // if(! Primes::isPrime(4)) { //if this number
82 // cout<<"Four is not a prime number"<<endl; //is not prime
83 // BB = Primes::factor(4); //than factor it
84 //
85 // if( BB[0] != Primes::smallestPrimeFactor(4) ){ //check that first
86 // //factor equals
87 // cerr<<"something is wrong"<<endl; //the smallest
88 // }
89 // cout<<"4 factored:"<<endl;
90 // for ( i = 0; i < BB.nelements(); i++ ) {
91 // cout<<BB[i]<<endl;
92 // }
93 //
94 // C = Primes::aLargerPrimeThan(4);
95 // if ( (C-5) > 4 ) { //if difference is more
96 // //than five, then
97 // C = Primes::nextLargerPrimeThan(4); //find next lprime
98 // }
99 // DebugAssertExit( C == Primes::aLargerPrimeThan(4)); //now the prime resides
100 // } //in the cache table
101 // if( Primes::nCachedPrimes() > 50 ) {
102 // Primes::initializeCache();
103 // }
104 // DD = Primes::cachedPrimes();
105 // cout<<"The Table of Primes"<<endl;
106 // for ( i = 0; i < Primes::nCachedPrimes(); i++ ) {
107 // cout<<DD[i]<<endl;
108 // }
109 // return 0;
110 // }
111 //
112 // </srcblock>
113 // </example>
114 //
115 // <motivation>
116 // This class was conceived during the coding of a class that creates hash
117 // tables. The hash table class works best with a table whose size is prime.
118 // It uses the Primes class's function "nextLargerPrimeThan" to find a prime
119 // number that is close to an appropriate size. This prime number becomes the
120 // size of the hash table.
121 // </motivation>
122 //
123 // <todo asof="$DATE:$">
124 // <li> This class should not be used to generate large sets of prime
125 // numbers - it is not designed for efficiency at this.
126 // The algorithm checks 2, 3, and (6n +/- 1) up to the square
127 // root of the candidate prime.
128 // <li> The size of the prime numbers are restricted by the size of an
129 // unsigned integer (2^31-1 on 32 bit machines).
130 // </todo>
131 
132 class Primes {
133 public:
134 
135  //This function takes number and returns "True" if number is prime, "False"
136  //if it is not.
137  static Bool isPrime(uInt number);
138 
139  //This function returns the closest integer larger than number from the
140  //table of primes. If there is no entry in the table of primes which is
141  //larger than number, a zero is returned.
142  static uInt aLargerPrimeThan(uInt number);
143 
144  //This function finds the next largest prime than number, returns that
145  //value and stores it in the table of primes.
146  static uInt nextLargerPrimeThan(uInt number); // adds to cache
147 
148  //This function returns the smallest factor of number.
149  static uInt smallestPrimeFactor(uInt number);
150 
151  //This function returns a block, of variable length, with each factor
152  //indexed. For example, if number equaled 4, then the return block would
153  //have a length of two, and have a two stored in each cell. One and zero
154  //are special cases; this function returns a one-cell block which holds
155  //one or zero, respectively.
156  static Block<uInt> factor(uInt number);
157 
158  // This function returns the number of primes stored in the primes table.
159  // static uInt nCachedPrimes()
160  // { return cacheTable.nelements(); }
161 
162  //This function returns the table of prime numbers.
163  //static Block<uInt> cachedPrimes()
164  // { return cacheTable; }
165 
166 private:
167 
168  //This function resets the table of prime numbers to contain 31 prime
169  //numbers to avoid consuming too much memory.
170  static void initializeCache();
171 
172  //This is the table which stores the prime numbers.
175 };
176 
177 
178 } //# NAMESPACE CASACORE - END
179 
180 #endif
static Mutex theirMutex
Definition: Primes.h:174
static uInt aLargerPrimeThan(uInt number)
This function returns the closest integer larger than number from the table of primes.
static void initializeCache()
This function returns the number of primes stored in the primes table.
static uInt smallestPrimeFactor(uInt number)
This function returns the smallest factor of number.
static Block< uInt > cacheTable
This is the table which stores the prime numbers.
Definition: Primes.h:173
static Block< uInt > factor(uInt number)
This function returns a block, of variable length, with each factor indexed.
static uInt nextLargerPrimeThan(uInt number)
This function finds the next largest prime than number, returns that value and stores it in the table...
static Bool isPrime(uInt number)
This function takes number and returns "True" if number is prime, "False" if it is not.
this file contains all the compiler specific defines
Definition: mainpage.dox:28
unsigned int uInt
Definition: aipstype.h:51
bool Bool
Define the standard types used by Casacore.
Definition: aipstype.h:42