// This program expects a number specified by the // user to specify the upper limit to the list of // primes. Optionally, a second argument of '1', // 't', or 'T' can turn on debugging to show the // processing difference optimization makes. This // code is based on code by Amit Khandelwal located // in the Java code here: // http://www.geeksforgeeks.org/sieve-of-eratosthenes/ // Updated to add optimization and input debugging // option. import java.util.Scanner; import java.lang.Math; // ********************* Program ******************** // // This is the main class of my prime package. public class Program { // Reasonable upper maximum of numbers to check. // This could be changed, if you really wished to. static final int upper = 500; // True, when debugging output is desired. // The code will display each of the current // elements as it is processed in the outer // loop and the corresponding multiples being // changed to not prime in the inner loop. // Plus, run both methods (without and with // optimizations.) If you turn on debugging, // don't process too many numbers. I suggest // 15 as it shows the optimization nicely. static boolean debug = false; // Number of primes to output on a single line. static final int outMax = 10; // ******************** soe ******************** // // This method implements the 'Sieve of // Eratosthenes' algorithm to find prime // numbers and print them. // // Arguments // n is the maximum number to check. // // Returns // Nothing. // // Catches // Nothing. // // Exceptions // Nothing. static void soe(int n) { final int max = n-1; // Maximum array elements // Create a boolean array containing the prime // status of 2 through n (array indexes 0 to // n-2) and initialize it to all numbers might // be prime (p is the array index.) boolean[] prime = new boolean[max]; for (int p = 0; p < max; p++) { prime[p] = true; } // for // For each element in the first half of the // array, check it out (p is the array index and // h is the half way point). for (int p = 0, h = n/2-2; p <= h; p++) { // Process the number (p+2). If the current // array element is still prime, this number // is a prime so any of it's multiples can't // be prime. if (debug) System.out.println("\nProcessing "+(p+2)+ " "+prime[p]); if (prime[p]) { // For each multiple of the current number, // update it's array element to not prime // (v is the current number and i is the // next multiple array index.) for (int v = p+2, i = v*2-2; i < max; i += v) { prime[i] = false; if (debug) System.out.println("Changed "+(i+2)); } // for } // if } // for // Output all prime numbers. Output the range // we checked. For each element in the array // that is a prime, output it's number (i is // the array index and c is the count of // how many primes have been listed on the // current output line.) System.out.println("\nFollowing are the prime numbers between 2 and "+n+":"); for (int i = 0, c = 0; i < max; i++) { if (prime[i]) { // The current number (i+2) is prime so // calculate the number (v) and spacing // needed to keep columns lined up (s), // output the spacing & number, increment // the count of primes on the current // output line, and, if we have outputted // enough, finish the current line & reset // the count for the next line. int v = i+2; String s = (v < 10)?" ":(v < 100)?" ":" "; System.out.print(s+v); if (++c == outMax) { System.out.println(); c = 0; } // if } // if } // for // Finish the current line. Don't really need // to, when the line doesn't have any primes, // but it doesn't hurt so why bother making // the count available here and testing it. System.out.println(); } // soe // ******************** osoe ******************** // // This method implements the 'Sieve of // Eratosthenes' algorithm to find prime // numbers and print them with optimizations of // stopping at the square root of n in the outer // loop & ignoring multiples less than prime^2 in // the inner loop. // // Arguments // n is the maximum number to check. // // Returns // Nothing. // // Catches // Nothing. // // Exceptions // Nothing. static void osoe(int n) { final int max = n-1; // Maximum array elements // Create a boolean array containing the prime // status of 2 through n (array indexes 0 to // n-2) and initialize it to all numbers might // be prime (p is the array index.) boolean[] prime = new boolean[max]; for (int p = 0; p < max; p++) { prime[p] = true; } // for // For each element of the array up to the // square root of the number as that is the // highest prime that can be a factor of the // range to be checked, check it out (p is // the array index and s is stopping point). for (int p = 0, s = (int)Math.sqrt(n)-2; p <= s; p++) { // Process the number (p+2). If the current // array element is still prime, this number // is a prime so any of it's multiples can't // be prime. if (debug) System.out.println("\nProcessing "+(p+2)+ " "+prime[p]); if (prime[p]) { // For each multiple of the current number // starting at it's square (as the lower // multiples are also multiples of a // lower prime), update it's array element // to not prime (v is the current number // and i is the next multiple array index.) for (int v = p+2, i = v*v-2; i < max; i += v) { prime[i] = false; if (debug) System.out.println("Changed "+(i+2)); } // for } // if } // for // Output all prime numbers. Output the range // we checked. For each element in the array // that is a prime, output it's number (i is // the array index and c is the count of // how many primes have been listed on the // current output line.) System.out.println("\nFollowing are the prime numbers between 2 and "+n+" using optimized sieve:"); for (int i = 0, c = 0; i < max; i++) { if (prime[i]) { // The current number (i+2) is prime so // calculate the number (v) and spacing // needed to keep columns lined up (s), // output the spacing & number, increment // the count of primes on the current // output line, and, if we have outputted // enough, finish the current line & reset // the count for the next line. int v = i+2; String s = (v < 10)?" ":(v < 100)?" ":" "; System.out.print(s+v); if (++c == outMax) { System.out.println(); c = 0; } // if } // if } // for // Finish the current line. Don't really need // to, when the line doesn't have any primes, // but it doesn't hurt so why bother making // the count available here and testing it. System.out.println(); } // osoe // ******************** main ******************** // // The main entry point of the Program class of the // prime package outputting primes from 2 to the // user's specified maximum. // // Arguments // args: An array of strings that is ignored. // // Returns // Nothing. // // Catches // A NoSuchElementException, when end of file was // reached instead of a number. // An InputMismatchException, when a non-digit // was read. // // Exceptions // Nothing. public static void main(String args[]) { // Set up to process the primes catching any // exception. try { int number; // User's maximum number String option; // Optional debug // Create a scanner to read the user's number, // prompt for, and read an integer. Scanner scan = new Scanner(System.in); System.out.print("Enter a number: "); number = scan.nextInt(); // If the debug optional argument was added, // read it, get the first character (c), set // debug as needed, and in both cases, close // the scanner. if (scan.hasNext()) { option = scan.next(); char c = option.charAt(0); debug = (c == '1' || c == 't' || c == 'T'); } // if scan.close(); // If the maximum number to check is // reasonable, process the primes. Have to // have at least one for the array allocation // to work so 2 is the minimum. If debug, // display both versions so user can see // the processing difference. if (number >= 2 && number <= upper) { if (debug) soe(number); osoe(number); // Otherwise, complain. } else { System.out.println( "\nNumber must be between 2 & "+upper+"!"); } // if // Catch any exception and complain. } catch (Exception e) { System.out.println("\nInvalid number!"); } // try } // main } // class Program

primes mn