Primes Namespace Reference

Functions
size_t	next_prime (unsigned long n)
	Find the smallest prime number >= n from the database.
bool	check_primes_database ()
	Verify the integrity of the prime database.
bool	is_prime (unsigned long n)
	Test if a number is prime using trial division.
unsigned long	next_prime_number_greater_than (unsigned long n)
	Find the next prime strictly greater than n.

Variables
const unsigned long	primeList []
	Pre-computed array of prime numbers for fast lookup.
const size_t	numPrimes = sizeof(primeList) / sizeof(primeList[0])
	Number of primes in the pre-computed database.
const unsigned long	DefaultPrime = primeList[0]
	Default prime number used when no specific size is requested.

Function Documentation

check_primes_database()

bool Primes::check_primes_database

(

)

Verify the integrity of the prime database.

Checks that all numbers in primeList are actually prime. Used for testing and validation.

Returns

true if all entries in primeList are prime

Definition at line 411 of file primes.C.

References numPrimes, and primeList.

Referenced by TEST().

is_prime()

bool Primes::is_prime ( unsigned long  n )

inline

Test if a number is prime using trial division.

Checks divisibility by all integers from 2 to sqrt(n).

Parameters

n	Number to test for primality

Returns

true if n is prime, false otherwise

Note

O(sqrt(n)) complexity - use next_prime() for hash table sizing

Example

Primes::is_prime(17);  // true
Primes::is_prime(18);  // false
Primes::is_prime(2);   // true
Primes::is_prime(1);   // false

Definition at line 128 of file primes.H.

References sqrt().

Referenced by next_prime(), next_prime_number_greater_than(), TEST(), TEST(), and TEST().

next_prime()

unsigned long Primes::next_prime

(

unsigned long

n

)

Find the smallest prime number >= n from the database.

Performs binary search on the pre-computed prime database to find a suitable prime for hash table sizing.

Parameters

n	Minimum value for the prime

Returns

Smallest prime p such that p >= n

Note

Uses pre-computed database, O(log numPrimes) complexity

Definition at line 383 of file primes.C.

References is_prime(), next_prime_number_greater_than(), and primeList.

Referenced by OhashCommon< HashTbl, Key >::check_resize_before_insert(), Aleph::GenLhashTable< Key, BucketType, Cmp >::insert(), Aleph::GenLhashTable< Key, BucketType, Cmp >::remove(), OhashCommon< HashTbl, Key >::remove_ptr(), Aleph::GenLhashTable< Key, BucketType, Cmp >::search_or_insert(), and TEST().

next_prime_number_greater_than()

unsigned long Primes::next_prime_number_greater_than ( unsigned long  n )

inline

Find the next prime strictly greater than n.

Unlike next_prime() which uses a database, this function computes primes dynamically using trial division. Useful when the database doesn't contain large enough primes.

Parameters

n	Find prime greater than this value

Returns

Smallest prime p such that p > n

Exceptions

std::domain_error

if n is too large (would overflow)

Note

O(sqrt(p) * (p-n)/2) worst case - slower than next_prime()

Example

next_prime_number_greater_than(10);   // 11
next_prime_number_greater_than(11);   // 13
next_prime_number_greater_than(100);  // 101

Definition at line 161 of file primes.H.

References ah_domain_error_if, is_prime(), and max().

Referenced by next_prime().

Variable Documentation

DefaultPrime

const unsigned long Primes::DefaultPrime = primeList[0]

Default prime number used when no specific size is requested.

Definition at line 381 of file primes.C.

Referenced by OhashCommon< HashTbl, Key >::empty().

numPrimes

const size_t Primes::numPrimes = sizeof(primeList) / sizeof(primeList[0])

Number of primes in the pre-computed database.

Definition at line 379 of file primes.C.

Referenced by check_primes_database(), TEST(), and TEST().

primeList

const unsigned long Primes::primeList

Pre-computed array of prime numbers for fast lookup.

Definition at line 45 of file primes.C.

Referenced by check_primes_database(), next_prime(), TEST(), and TEST().