ISC Practicals and Theory - Sieve of Eratosthenes

The Sieve of Eratosthenes is a method of finding every prime number up to a limit $n$ without testing each number separately. We write down all the numbers from 2 to $n$, then cross out the multiples of each prime in turn. The numbers that are never crossed out are the primes. This program, written in the main method alone, reads $n$, crosses out composites in a boolean array and prints all the primes up to $n$ together with their count.

Definition

A prime number is a number greater than 1 whose only factors are 1 and itself. A composite number is a number greater than 1 that has some other factor.

The sieve works because every composite number is a multiple of a smaller prime. If we cross out the multiples of 2, then of 3, then of 5 and so on, only primes remain.

For $n = 30$:

• Cross out the multiples of 2: 4, 6, 8, ..., 30.
• The next number not crossed out is 3. Cross out its multiples: 9, 15, 21, 27 are new (the rest are already gone).
• The next is 5. Cross out 25 (30 is already gone).
• The next is 7, but $7 \times 7 = 49$ is more than 30, so nothing is left to cross out.
• Primes left: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, so there are 10 primes.

Why start from $p \times p$: a multiple $p \times k$ with $k < p$ has the smaller factor $k$, so it was already crossed out when we handled the primes below $p$. The first multiple of $p$ that can be new is $p \times p$. For the same reason we only need to take $p$ while $p \times p \le n$.

Range: the program accepts $n$ from 2 to 1000, and otherwise prints an error message.

Algorithm

1. Read n. If it is not from 2 to 1000, print an error message and stop.
2. Create the boolean array composite of size n + 1. All elements are false at the start: nothing is crossed out.
3. For p from 2 while p * p <= n: if composite[p] is still false, then p is prime. Cross out its multiples, starting from p * p (the smaller multiples were crossed out by smaller primes), by setting composite[m] = true for m = p * p, p * p + p, ... up to n.
4. Go through i from 2 to n and print every i with composite[i] still false; these are the primes. Count them in count.
5. Print the count of primes.

Program

In main, the nested for loops cross out the multiples of each prime and the last for loop prints the numbers that were not crossed out.

import java.util.Scanner;
public class Sieve
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);   // reads the input from the keyboard
        System.out.print("Enter n (2 to 1000): ");
        int n = sc.nextInt();                  // upper limit up to which primes are to be found
        if (n < 2 || n > 1000)
        {
            System.out.println("Invalid input. n must be from 2 to 1000.");
        }
        else
        {
            boolean[] composite = new boolean[n + 1];   // composite[i] is true once i has been crossed out; all false at the start
            for (int p = 2; p * p <= n; p++)
            {
                if (!composite[p])             // p is still not crossed out, so p is prime
                {
                    for (int m = p * p; m <= n; m = m + p)
                    {
                        composite[m] = true;
                    }
                }
            }
            int count = 0;                     // number of primes found
            System.out.println("Prime numbers up to " + n + ":");
            for (int i = 2; i <= n; i++)
            {
                if (!composite[i])
                {
                    System.out.print(i + " ");
                    count++;
                }
            }
            System.out.println();
            System.out.println("Count of primes = " + count);
        }
    }
}

Variable description table

Sample input and output

Enter n (2 to 1000): 30
Prime numbers up to 30:
2 3 5 7 11 13 17 19 23 29 
Count of primes = 10

Enter n (2 to 1000): 2
Prime numbers up to 2:
2 
Count of primes = 1

Enter n (2 to 1000): 97
Prime numbers up to 97:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
Count of primes = 25

Enter n (2 to 1000): 1
Invalid input. n must be from 2 to 1000.

Dry run

Input: n = 30. The array composite has indexes 0 to 30, all false at the start.

The printing loop now goes through i = 2 to 30 and prints those not crossed out: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Here count goes from 0 to 10, so the last line is Count of primes = 10. This matches the output of the first sample run.

Variations

1. Range "Print all prime numbers between m and n using the Sieve of Eratosthenes."
2. Twin primes "Using the sieve, print all pairs of twin primes (primes that differ by 2) up to n."
3. Sum of primes "Find the sum of all primes up to n using the sieve."
4. Largest prime "Find the largest prime number not more than n using the sieve."