Package org.nevec.rjm

Class 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
    Author:
    Richard J. Mathar

    • 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

      All Methods Static Methods Instance Methods Concrete Methods 
      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