## Saturday, 21 January 2017

### Chapter 22 Exercise 14, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

22.14 (Execution time for prime numbers) 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.

public class Exercise14 {

public static void main(String[] args) {
int begin = 8_000_000;
int end = 18_000_000;
int step = 2_000_000;

System.out.print("\t\t|");
for (int n = begin; n <= end; n += step) {
System.out.printf("%15d", n);
}
System.out.println();
System.out.println("----------------|-------------------------------------------------------------------------------------------");
System.out.print("Listing 24.4\t|");
for (int n = begin; n <= end; n += step) {
long startTime = System.currentTimeMillis();
getPrime1(n);
long endTime = System.currentTimeMillis();
long executionTime = (endTime - startTime) / 1000;
System.out.printf("%15d", executionTime);
}
System.out.println();
System.out.println("----------------|-------------------------------------------------------------------------------------------");
System.out.print("Listing 24.5\t|");
for (int n = begin; n <= end; n += step) {
long startTime = System.currentTimeMillis();
getPrime2(n);
long endTime = System.currentTimeMillis();
long executionTime = (endTime - startTime) / 1000;
System.out.printf("%15d", executionTime);
}
System.out.println();
System.out.println("----------------|-------------------------------------------------------------------------------------------");
System.out.print("Listing 24.6\t|");
for (int n = begin; n <= end; n += step) {
long startTime = System.currentTimeMillis();
getPrime3(n);
long endTime = System.currentTimeMillis();
long executionTime = (endTime - startTime) / 1000;
System.out.printf("%15d", executionTime);
}

}

public static int getPrime1(int n) {
int count = 0;
int number = 2;
while (number <= n) {
boolean isPrime = true;
for (int divisor = 2; divisor <= (int) (Math.sqrt(number)); divisor++) {
if (number % divisor == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
count++;
}
number++;
}
return count;
}

public static int getPrime2(int n) {
java.util.List<Integer> list = new java.util.ArrayList<Integer>();
int count = 0;
int number = 2;
int squareRoot = 1;
while (number <= n) {
boolean isPrime = true;
if (squareRoot * squareRoot < number)
squareRoot++;
for (int k = 0; k < list.size() && list.get(k) <= squareRoot; k++) {
if (number % list.get(k) == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
count++;
}
number++;
}
return count;
}

public static int getPrime3(int n) {
boolean[] primes = new boolean[n + 1];
for (int i = 0; i < primes.length; i++) {
primes[i] = true;
}
for (int k = 2; k <= n / k; k++) {
if (primes[k]) {
for (int i = k; i <= n / k; i++) {
primes[k * i] = false;
}
}
}
int count = 0;
for (int i = 2; i < primes.length; i++) {
if (primes[i]) {
count++;
}
}
return count;
}
}