Package etomica.veos.bigdecimal

Class Prime

java.lang.Object

etomica.veos.bigdecimal.Prime

public class Prime
extends java.lang.Object

Prime numbers. The implementation is a very basic computation of the set of all primes on demand, growing infinitely without any defined upper limit. The effects of such scheme are (i) the lookup-times become shorter after a while as more and more primes have been used and stored. The applications appear to become faster. (ii) Using the implementation for factorizations may easily require all available memory and stall finally, because indeed a dense list of primes with growing upper bound is kept without any hashing or lagging scheme.

Since:

2006-08-11

Field Summary

Fields

Modifier and Type	Field	Description
protected static java.math.BigInteger	nMax	The maximum integer covered by the high end of the list.

Constructor Summary

Constructors

Constructor	Description
Prime()	Default constructor initializing a list of primes up to 17.

Method Summary

Modifier and Type	Method	Description
java.math.BigInteger	at(int i)	return the ithprime
boolean	contains(java.math.BigInteger n)	Test if a number is a prime.
protected void	growto(java.math.BigInteger n)	extend the list of known primes up to n
boolean	isSPP(java.math.BigInteger n, java.math.BigInteger a)	Test whether a number n is a strong pseudoprime to base a.
static void	main(java.lang.String[] args)	Test program.
int	millerRabin(java.math.BigInteger n)	Miller-Rabin primality tests.
java.math.BigInteger	nextprime(java.math.BigInteger n)	return the smallest prime larger than n
java.math.BigInteger	pi(java.math.BigInteger n)	return the count of primes <= n
java.math.BigInteger	prevprime(java.math.BigInteger n)	return the largest prime smaller than n

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

nMax

protected static java.math.BigInteger nMax

The maximum integer covered by the high end of the list.

Constructor Detail

Prime

public Prime()

Default constructor initializing a list of primes up to 17. 17 is enough to call the Miller-Rabin tests on the first 7 primes without further action.

Method Detail

contains

public boolean contains(java.math.BigInteger n)

Test if a number is a prime.

Parameters:

n - the integer to be tested for primality

Returns:

true if prime, false if not

isSPP

public boolean isSPP(java.math.BigInteger n,
                     java.math.BigInteger a)

Test whether a number n is a strong pseudoprime to base a.

Parameters:

n - the integer to be tested for primality

a - the base

Returns:

true if the test is passed, so n may be a prime. false if the test is not passed, so n is not a prime.

Since:

2010-02-25

millerRabin

public int millerRabin(java.math.BigInteger n)

Miller-Rabin primality tests.

Parameters:

n - The prime candidate

Returns:

-1 if n is a composite, 1 if it is a prime, 0 if it may be a prime.

Since:

2010-02-25

at

public java.math.BigInteger at(int i)

return the ithprime

Parameters:

i - the zero-based index into the list of primes

Returns:

the ith prime. This is 2 if i=0, 3 if i=1 and so forth.

pi

public java.math.BigInteger pi(java.math.BigInteger n)

return the count of primes <= n

Parameters:

n - the upper limit of the scan

Returns:

the ith prime. This is 2 if i=0, 3 if i=1 and so forth.

nextprime

public java.math.BigInteger nextprime(java.math.BigInteger n)

return the smallest prime larger than n

Parameters:

n - lower limit of the search

Returns:

the next larger prime.

Since:

2008-10-16

prevprime

public java.math.BigInteger prevprime(java.math.BigInteger n)

return the largest prime smaller than n

Parameters:

n - upper limit of the search

Returns:

the next smaller prime.

Since:

2008-10-17

growto

protected void growto(java.math.BigInteger n)

extend the list of known primes up to n

Parameters:

n - the maximum integer known to be prime or not prime after the call.

main

public static void main(java.lang.String[] args)
                 throws java.lang.Exception

Test program. Usage: java -cp . org.nevec.rjm.Prime n
This takes a single argument (n) and prints prime(n), the previous and next prime, and pi(n).

Throws:

java.lang.Exception

Since:

2006-08-14