1.15 Computing Primes

Example 1-15 computes the largest prime number less than a specified value, using the Sieve of Eratosthenes algorithm. The algorithm finds primes by eliminating multiples of all lower prime numbers. Like Example 1-14, this example introduces no new Java syntax, but is a nice, nontrivial program with which to end this chapter. The program may seem deceptively simple, but there's actually a fair bit going on, so be sure you understand how it is ruling out prime numbers.

Example 1-15. Sieve.java

package je3.basics; /**  * This program computes prime numbers using the Sieve of Eratosthenes  * algorithm: rule out multiples of all lower prime numbers, and anything  * remaining is a prime.  It prints out the largest prime number less than  * or equal to the supplied command-line argument.  **/ public class Sieve {     public static void main(String[  ] args) {         // We will compute all primes less than the value specified on the         // command line, or, if no argument, all primes less than 100.         int max = 100;                           // Assign a default value         try { max = Integer.parseInt(args[0]); } // Parse user-supplied arg         catch (Exception e) {  }                   // Silently ignore exceptions.         // Create an array that specifies whether each number is prime or not.         boolean[  ] isprime = new boolean[max+1];         // Assume that all numbers are primes, until proven otherwise.         for(int i = 0; i <= max; i++) isprime[i] = true;         // However, we know that 0 and 1 are not primes.  Make a note of it.         isprime[0] = isprime[1] = false;         // To compute all primes less than max, we need to rule out         // multiples of all integers less than the square root of max.         int n = (int) Math.ceil(Math.sqrt(max));  // See java.lang.Math class         // Now, for each integer i from 0 to n:         //   If i is a prime, then none of its multiples are primes,         //   so indicate this in the array.  If i is not a prime, then         //   its multiples have already been ruled out by one of the         //   prime factors of i, so we can skip this case.         for(int i = 0; i <= n; i++) {             if (isprime[i])                          // If i is a prime,                  for(int j = 2*i; j <= max; j = j + i) // loop through multiples                     isprime[j] = false;               // they are not prime.         }         // Now go look for the largest prime:         int largest;         for(largest = max; !isprime[largest]; largest--) ;  // empty loop body                  // Output the result         System.out.println("The largest prime less than or equal to " + max +                            " is " + largest);     } }