Primes.java   [plain text]

// Primes.java

/** Copyright 1998
 * Roedy Green
 * Canadian Mind Products
 * 5317 Barker Avenue
 * Burnaby, BC Canada V5H 2N6
 * tel: (604) 435-3016
 * mailto:roedy@mindprod.com
 * http://mindprod.com
 */
// May be freely distributed for any purpose but military

import java.util.BitSet;

/**
  * @author Roedy Green
  * @version 1.10 1998 November 10
  * Calculate primes using Eratostheses Sieve.
  * Tell if a given number is prime.
  * Find a prime just below a given number.
  * Find a prime just above a given number.
  */
  
/* 
 * version 1.1 1998 November 10 - new address and phone.  
 */
class Primes
    {

    /**
      * constructors
      */
    Primes()
        {
        ensureCapacity(1000);
        }

    /**
      * @param capacity - largest number you will be asking if prime.
      * If give too small a number, it will automatically grow by
      * recomputing the sieve array.
      */
    Primes (int capacity)
        {
        ensureCapacity(capacity);
        }

    /**
      * @param candidate - is this a prime?
      */
    public boolean isPrime(int candidate)
        {
        ensureCapacity(candidate);
        if (candidate < 3) return candidate != 0;
        if (candidate % 2 == 0 ) return false;
        return !b.get(candidate/2);
        }

    /**
      * @return first prime higher than candidate
      */
    public int above(int candidate)
    {
        do
            {
            // see what we can find in the existing sieve
            for (int i=candidate+1; i<= sieveCapacity; i++)
                {
                if (isPrime(i)) return i;
                }
            // Keep building ever bigger sieves till we succeed.
            // The next prime P' is between P+2 and P^2 - 2.
            // However that is a rather pessimistic upper bound.
            // Ideally some theorem would tell us how big we need to build
            // to find one.
            ensureCapacity(Math.max(candidate*2, sieveCapacity*2));
            } // end do
        while (true);
        } // end above

    /**
      * @param return first prime less than candidate
      */
    public int below (int candidate)
    {
        for (candidate--; candidate > 0; candidate--)
            {
            if (isPrime(candidate)) return candidate;
            }
        // candidate was 1 or 0 or -ve
        return 0;
        }

    /**
      * calc all primes in the range 1..n,
      * not the first n primes.
      * @param n, highest candidate, not necessarily prime.
      * @return list of primes 1..n in an array
      */
    public final int[] getPrimes(int n)
        {
        // calculate the primes
        ensureCapacity(n);

        // pass 1: count primes
        int countPrimes = 0;
        for (int i = 0; i <= n; i++)
            {
            if (isPrime(i)) countPrimes++;
            }

        // pass 2: construct array of primes
        int [] primes = new int[countPrimes];
        countPrimes = 0;
        for (int i = 0; i <= n; i++)
            {
            if (isPrime(i)) primes[countPrimes++] = i;
            }
        return primes;
        } // end getPrimes

    /**
      * calculate the sieve, bit map of all primes 0..n
      * @param n highest number evalutated by the sieve, not necessarily prime.
      */
    private final void sieve ( int n )
        {
        // Presume BitSet b set is big enough for our purposes.
        // Presume all even numbers are already marked composite, effectively.
        // Presume all odd numbers are already marked prime (0 in bit map).
        int last = (int)(Math.sqrt(n))+1;
        for (int candidate = 3; candidate <= last; candidate += 2)
            {
            // only look at odd numbers
            if (!b.get(candidate/2) /* if candidate is prime */)
                {
                // Our candidate is prime.
                // Only bother to mark multiples of primes. Others already done.
                // no need to mark even multiples, already done
                int incr = candidate*2;
                for ( int multiple = candidate + incr; multiple < n; multiple += incr)
                    {
                    b.set(multiple/2); // mark multiple as composite
                    } // end for multiple
                } // end if
            } // end for candidate
        // at this point our sieve b is correct, except for 0..2
        } // end sieve

    /**
      * Ensure have a sieve to tackle primes as big as n.
      * If we don't allocate a sieve big enough and calculate it.
      * @param n - ensure sieve big enough to evaluate n for primality.
      */
    private void ensureCapacity (int n)
        {
        if ( n > sieveCapacity )
            {
            b = new BitSet((n+1)/2);
            // starts out all 0, presume all numbers prime
            sieveCapacity = n;
            sieve(n);
            }
        // otherwise existing sieve is fine
        } // end ensureCapacity

    private int sieveCapacity;
    // biggest number we have computed in our sieve.
    // our BitSet array is indexed 0..N (odd only)

    private BitSet b; /* true for each odd number if is composite */

    /**
      * Demonstrate and test the methods
      */
    public static void main (String[] args)
        {
        // print primes 1..101
        Primes calc = new Primes(106);
        int[] primes = calc.getPrimes(101);
        for (int i=0; i<primes.length; i++)
            {
            System.out.println(primes[i]);
            }

        // demonstrate isPrime, above, below
        System.out.println(calc.isPrime(149));
        System.out.println(calc.below(149));
        System.out.println(calc.above(149));

        // print all the primes just greater than powers of 2
        calc = new Primes(10000000);
        for (int pow=8; pow < 10000000; pow*=2)
            System.out.println(calc.above(pow));

        // Validate that isPrime works by comparing it with brute force
        for (int i=3; i<=151; i++)
            {
            boolean prime = true;
            for (int j=2; j<i; j++)
                {
                if (i % j == 0 )
                    {
                    prime = false;
                    break;
                    }
                } // end for j
            if ( calc.isPrime(i) != prime ) System.out.println(i + " oops");
            } // end for i

        } // end main
} // end Primes