Write a program that obtains the execution time for finding all the prime numbers less than 8,000,000, 10,000,000, 12,000,000, 14,000,000, 16,000,000, and 18,000,000 using the algorithms in Listings 22.5?22.7. Your program should print a table like this:

Listing 22.5PrimeNumbers.java

Listing 22.6EfficientPrimeNumbers.java

Listing 22.7SieveOfEratosthenes.java

Transcribed Image Text:

10000000 8000000 12000000 14000000 16000000 18000000 Listing 22.5 Listing 22.6 Listing 22.7 import java.util.Scanner; 3 public class PrimeNumbers { public static void main(String[] args) { Scanner input = new Scanner(System. in); System.out.print("Find all prime numbers = n, enter n: "); int n - input.nextInt (); 10 11 final int NUMBER_PER_LINE = 10; // Display 10 per line int count = 0; // Count the number of prime numbers int number = 2; // A number to be tested for primeness 12 13 System.out.println("The prime numbers are:"); 14 15 16 // Repeatedly find prime numbers while (number <= n) { // Assume the number is prime boolean isPrime - true; // Is the current number prime? 17 18 19 20 21 // Test if number is prime for (int divisor = 2; divisor <= (int) (Math.sqrt(number)); divisor++) { if (number % divisor =- 0) { // If true, number is not prime isPrime - false; // Set isPrime to false break; // Exit the for loop check prime 22 23 24 25 26 27 28 29 // Print the prime number and increase the count if (isPrime) { count++; // Increase the count increase count 30 31 32 if (count % NUMBER_PER_LINE == 0) { // Print the number and advance to the new line System.out.printf("%7d\n", number); 33 34 35 36 37 else 38 System.out.printf("%7d", number); 39 40 41 42 43 // Check if the next number is prime number++; check next number 44 45 46 47 48 } System.out.println("\n" + count + prime(s) less than or equal to + n);