/* * [Primes.java] * * Summary: calculate primes or a prime near a given number. * * Copyright: (c) 1998-2017 Roedy Green, Canadian Mind Products, http://mindprod.com * * Licence: This software may be copied and used freely for any purpose but military. * http://mindprod.com/contact/nonmil.html * * Requires: JDK 1.8+ * * Created with: JetBrains IntelliJ IDEA IDE http://www.jetbrains.com/idea/ * * Version History: * 1.1 1998-11-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. * new address and phone. * 1.2 2006-01-29 import to Eclipse and tidy. * 1.3 2006-02-01 * 1.4 2006-03-06 reformat with IntelliJ, add Javadoc. */ package com.mindprod.primes; import java.util.BitSet; import static java.lang.System.*; /** * calculate primes or a prime near a given number. * * @author Roedy Green, Canadian Mind Products * @version 1.4 2006-03-06 * @since 1998 */ final class Primes { private static final int FIRST_COPYRIGHT_YEAR = 1998; /** * not displayed copyright */ private static final String EMBEDDED_COPYRIGHT = "Copyright: (c) 1998-2017 Roedy Green, Canadian Mind Products, http://mindprod.com"; private static final String RELEASE_DATE = "2006-03-06"; /** * embedded version string. */ private static final String VERSION_STRING = "1.4"; /** * true for each odd number if is composite */ private BitSet b; /** * how many elements max in the seize arra */ private int sieveCapacity; /** * 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. */ private Primes( int capacity ) { ensureCapacity( capacity ); } /** * @param candidate number you want to find a prime near. * * @return first prime higher than candidate */ 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 candidate number you want to find a prime near. * * @return first prime less than candidate */ int below( int candidate ) { for ( candidate--; candidate > 0; candidate-- ) { if ( isPrime( candidate ) ) { return candidate; } } // candidate was 1 or 0 or -ve return 0; } // biggest number we have computed in our sieve. // our BitSet array is indexed 0..N (odd only) /** * 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 /** * 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 */ 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 /** * @param candidate - is this a prime? * * @return true if this number is prime */ boolean isPrime( int candidate ) { ensureCapacity( candidate ); if ( candidate < 3 ) { return candidate != 0; } return candidate % 2 != 0 && !b.get( candidate / 2 ); } /** * calculate the sieve, bit map of all primes 0..n * * @param n highest number evalutated by the sieve, not necessarily prime. */ private 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 /** * Demonstrate and test the methods * * @param args not used */ public static void main( String[] args ) { out.println( "primes under 10,000" ); Primes calc = new Primes( 10000 ); int[] primes = calc.getPrimes( 10000 ); for ( final int prime1 : primes ) { out.println( prime1 ); } // demonstrate isPrime, above, below out.println( "Is 149 prime? " + calc.isPrime( 149 ) ); out.println( "The prime just below 149 is " + calc.below( 149 ) ); out.println( "The prime just above 149 is " + calc.above( 149 ) ); out.println( "Primes just larger than 2^n" ); calc = new Primes( 10000000 ); for ( int pow = 8; pow < 10000000; pow *= 2 ) { out.println( calc.above( pow ) ); } out.println( "Validating that isPrime works by comparing it with brute force successive division." ); 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 ) { out.println( i + " oops: algorithms give different answers" ); } } // end for i out.println( "done" ); } // end main } // end Primes