DEVELOPING EFFICIENT ALGORITHMS - Introduction to Java Programming: Comprehensive Version - page 842

still true, then i is a prime number. As shown in Figure 22.3, 2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , and 23
are prime numbers. Listing 22.7 gives the program for finding the prime numbers using the
Sieve of Eratosthenes algorithm .

L ISTING 22.7

SieveOfEratosthenes.java
1 import java.util.Scanner;
2
3 public class SieveOfEratosthenes {
4 public static void main(String[] args) {
5 Scanner input = new Scanner(System.in);
6 System.out.print( "Find all prime numbers <= n, enter n: " );
7 int n = input.nextInt();

8
9

boolean [] primes = new boolean [n + 1 ]; // Prime number sieve sieve

10
11

// Initialize primes[i] to true

12 for ( int i = 0 ; i < primes.length; i++) {

13 primes[i] = true ; initialize sieve

14 }
15
16

for ( int k = 2 ; k <= n / k; k++) {

17 if (primes[k]) {

18 for ( int i = k; i <= n / k; i++) {

19 primes[k * i] = false ; // k * i is not prime nonprime

20 }
21 }
22 }
23
24 int count = 0 ; // Count the number of prime numbers found so far
25 // Print prime numbers
26 for ( int i = 2 ; i < primes.length; i++) {
27 if (primes[i]) {
28 count++;
29 if (count % 10 == 0 )
30 System.out.printf( "%7d\n" , i);
31 else
32 System.out.printf( "%7d" , i);
33 }
34 }
35
36 System.out.println( "\n" + count +
37

" prime(s) less than or equal to " + n);

38 }
39 }

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 16). Otherwise, k * i would be greater than n (line 19). What
is the time complexity of this algorithm?