Paul NgugiThis section presents several algorithms in the search for an efficient algorithm for finding prime numbers. Can you design a fast algorithm for finding prime numbers?
An integer greater than 1 is prime if its only positive divisor is 1 or itself. For example, 2, 3, 5, and 7 are prime numbers, but 4, 6, 8, and 9 are not.
How do you determine whether a number n is prime? PrimeNumber.java presented a brute-force algorithm for finding prime numbers. The algorithm checks whether 2, 3, 4, 5, . . . , or n - 1 is divisible by n. If not, n is prime. This algorithm takes O(n) time to check whether n is prime. Note that you need to check only whether 2, 3, 4, 5, . . . , and n/2 is divisible by n. If not, n is prime. This algorithm is slightly improved, but it is still of O(n).
In fact, we can prove that if n is not a prime, n must have a factor that is greater than 1 and less than or equal to sqrt(n). Here is the proof. Since n is not a prime, there exist two numbers p and q such that n = pq with 1 < p <= q. Note that n = sqrt(n)sqrt(n). p must be less than or equal to sqrt(n). Hence, you need to check only whether 2, 3, 4, 5, . . . , or sqrt(n) is divisible by n. If not, n is prime. This significantly reduces the time complexity of the algorithm to O(sqrt(n)).
Now consider the algorithm for finding all the prime numbers up to n. A straightforward implementation is to check whether i is prime for i = 2, 3, 4, . . . , n. The program is given in code below.
package demo;
import java.util.Scanner;
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();
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
System.out.println("The prime numbers are:");
// Repeatedly find prime numbers
while(number <= n) {
// Assume the number is prime
boolean isPrime = true; // Is the current number prime?
// 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
}
}
// Print the prime number and increase the count
if(isPrime) {
count++; // Increase the count
if(count % NUMBER_PER_LINE == 0) {
// Print the number and advance to the new line
System.out.printf("%7d\n", number);
}
else
System.out.printf("%7d", number);
}
// Check if the next number is prime
number++;
}
System.out.println("\n" + count + " prime(s) less than or equal to " + n);
}
}
Find all prime numbers <= n, enter n: 1000
The prime numbers are:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
...
...
168 prime(s) less than or equal to 1000
The program is not efficient if you have to compute Math.sqrt(number) for every iteration of the for loop (line 23). A good compiler should evaluate Math.sqrt(number) only once for the entire for loop. To ensure this happens, you can explicitly replace line 23 with the following two lines:
int squareRoot = (int)(Math.sqrt(number));
for (int divisor = 2; divisor <= squareRoot; divisor++) {
In fact, there is no need to actually compute Math.sqrt(number) for every number. You need look only for the perfect squares such as 4, 9, 16, 25, 36, 49, and so on. Note that for all the numbers between 36 and 48, inclusively, their (int)(Math.sqrt(number)) is 6. With this insight, you can replace the code in lines 18–27 with the following:
...
int squareRoot = 1;
// Repeatedly find prime numbers
while (number <= n) {
// Assume the number is prime
boolean isPrime = true; // Is the current number prime?
if (squareRoot * squareRoot < number) squareRoot++;
// Test if number is prime
for (int divisor = 2; divisor <= squareRoot; divisor++) {
if (number % divisor == 0) { // If true, number is not prime
isPrime = false; // Set isPrime to false
break; // Exit the for loop
}
}
...
Now we turn our attention to analyzing the complexity of this program. Since it takes sqrt(i) steps in the for loop (lines 23–28) to check whether number i is prime, the algorithm takes sqrt(2) + sqrt(3) + sqrt(4) + ... + sqrt(n) steps to find all the prime numbers less than or equal to n. Observe that
sqrt(2) + sqrt(3) + sqrt(4) + ... + sqrt(n) <= (n)sqrt(n)
Therefore, the time complexity for this algorithm is O((n)sqrt(n)).
To determine whether i is prime, the algorithm checks whether 2, 3, 4, 5, . . . , and 2i are divisible by i. This algorithm can be further improved. In fact, you need to check only whether the prime numbers from 2 to sqrt(i) are possible divisors for i.
We can prove that if i is not prime, there must exist a prime number p such that i = pq and p <= q. Here is the proof. Assume that i is not prime; let p be the smallest factor of i. p must be prime, otherwise, p has a factor k with 2 <= k < p. k is also a factor of i, which contradicts that p be the smallest factor of i. Therefore, if i is not prime, you can find a prime number from 2 to sqrt(i) that is divisible by i. This leads to a more efficient algorithm for finding all prime numbers up to n, as shown in the code below.
package demo;
import java.util.Scanner;
public class EfficientPrimeNumbers {
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();
// A list to hold prime numbers
java.util.List<Integer> list = new java.util.ArrayList<>();
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
int squareRoot = 1; // Check whether number <= squareRoot
System.out.println("The prime numbers are \n");
// Repeatedly find prime numbers
while(number <= n) {
// Assume the number is prime
boolean isPrime = true; // Is the current number prime?
if(squareRoot * squareRoot < number) squareRoot++;
// Test if number is prime
for(int k = 0; k < list.size() && list.get(k) <= squareRoot; k++) {
if(number % list.get(k) == 0) { // If true, not prime
isPrime = false; // Set isPrime to false
break; // Exit the for loop
}
}
// Print the prime number and increase the count
if(isPrime) {
count++; // Increase the count
list.add(number); // Add a new prime to the list
if(count % NUMBER_PER_LINE == 0) {
// Print the number and advance to the new line
System.out.println(number);
}
else
System.out.print(number + " ");
}
// Check whether the next number is prime
number++;
}
System.out.println("\n" + count + " prime(s) less than or equal to " + n);
}
}
Find all prime numbers <= n, enter n: 1000
The prime numbers are:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
...
...
168 prime(s) less than or equal to 1000
Let PI(i) denote the number of prime numbers less than or equal to i. The primes under 20 are 2, 3, 5, 7, 11, 13, 17, and 19. Therefore, PI(2) is 1, PI(3) is 2, PI(6) is 3, and PI(20) is 8.
It has been proved that PI(i) is approximately i / log(i).
For each number i, the algorithm checks whether a prime number less than or equal to sqrt(i) is divisible by i. The number of the prime numbers less than or equal to sqrt(i) is
sqrt(i) / (log)sqrt(i) = (2)sqrt(i) / logi
Thus, the complexity for finding all prime numbers up to n is
This algorithm is another example of dynamic programming. The algorithm stores the results of the subproblems in the array list and uses them later to check whether a new number is prime.
Is there any algorithm better than
O((n)sqrt(n) / logn)?
Let us examine the well-known Eratosthenes
algorithm for finding prime numbers. Eratosthenes (276–194 b.c.) was a Greek mathematician who devised a clever algorithm, known as the Sieve of Eratosthenes, for finding all prime numbers <= n. His algorithm is to use an array named primes of n Boolean values. Initially, all elements in primes are set true. Since the multiples of 2 are not prime, set primes[2 * i] to false for all 2 <= i <= n/2, as shown in Figure below. Since we don’t care about primes[0] and primes[1], these values are marked X in the figure.
Since the multiples of 3 are not prime, set primes[3 * i] to false for all 3 … i … n/3. Because the multiples of 5 are not prime, set primes[5 * i] to false for all 5 … i … n/5. Note that you don’t need to consider the multiples of 4, because the multiples of 4 are also the multiples of 2, which have already been considered. Similarly, multiples of 6, 8, and 9 need not be considered. You only need to consider the multiples of a prime number k = 2, 3, 5, 7, 11, . . . , and set the corresponding element in primes to false. Afterward, if primes[i] is still true, then i is a prime number. As shown in Figure below, 2, 3, 5, 7, 11, 13, 17, 19, and 23 are prime numbers. The cde below gives the program for finding the prime numbers using the Sieve of Eratosthenes algorithm.
Find all prime numbers <= n, enter n: 1000
The prime numbers are:
2 3 5 7 11 13 17 19 23 29
31 37 41 43 47 53 59 61 67 71
...
...
168 prime(s) less than or equal to 1000
Note that k <= n / k (line 17). Otherwise, k * i would be greater than n (line 20). What is the time complexity of this algorithm?
For each prime number k (line 18), the algorithm sets primes[k * i] to false (line 20). This is performed n / k – k + 1 times in the for loop (line 19). Thus, the complexity for finding all prime numbers up to n is
Table below summarizes the complexity of these three algorithms for finding all prime numbers up to n.
