ISC Practicals and Theory - Sieve of Eratosthenes (OOP)

The Sieve of Eratosthenes finds every prime number up to a limit $n$ by crossing out the multiples of each prime in a boolean array; the numbers left uncrossed are the primes. This version is written as a class Sieve with data members, a parameterised constructor and methods that each do one job, and main creates an object and calls them.

Definition

A prime number is a number greater than 1 whose only factors are 1 and itself; a composite number has some other factor. The sieve crosses out the multiples of each prime $p$, starting from $p \times p$ (smaller multiples such as $2p, 3p, \dots$ have a smaller prime factor and are already crossed out). It is enough to take $p$ while $p \times p \le n$.

For $n = 30$: crossing out the multiples of 2, 3 and 5 leaves 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, that is 10 primes. The range accepted is 2 to 1000.

Algorithm

1. main reads the limit into num and creates the object with new Sieve(num). The parameterised constructor Sieve(int nn) stores it in n, sets count to 0 and leaves composite empty for now.
2. isValid() returns true when $2 \le n \le 1000$. If it returns false, main prints an error message and stops.
3. crossOut() creates composite of size $n + 1$ (all false), then for p from 2 while p * p <= n:
   • if composite[p] is false, run m from p * p to $n$ in steps of p and set composite[m] = true.
4. countPrimes() counts the indexes from 2 to $n$ whose composite value is still false and returns that count.
5. display() prints those numbers and then the value returned by countPrimes().

Program

The constructor sets up the object, isValid() checks the range, crossOut() runs the sieve, countPrimes() returns how many primes there are and display() prints the result.

import java.util.Scanner;

/**
 * Class Sieve finds all prime numbers from 2 to n using the
 * Sieve of Eratosthenes. The limit is passed through the constructor.
 */
public class Sieve
{
    int n;               // upper limit up to which primes are to be found
    boolean[] composite; // composite[i] is true once i has been crossed out
    int count;           // number of primes found

    /**
     * Parameterised constructor.
     * @param nn the upper limit, stored in n
     */
    Sieve(int nn)
    {
        n = nn;
        composite = null;               // the array is created later, in crossOut()
        count = 0;
    }

    /**
     * Checks whether n is in the allowed range.
     * @return true if 2 <= n <= 1000, otherwise false
     */
    boolean isValid()
    {
        return n >= 2 && n <= 1000;
    }

    /** Crosses out the multiples of every prime p, starting from p * p. */
    void crossOut()
    {
        composite = new boolean[n + 1]; // size n + 1 so that index n exists; all false at the start
        // a composite number up to n has a factor not above sqrt(n)
        for (int p = 2; p * p <= n; p++)
        {
            if (!composite[p]) // p is not crossed out, so p is prime
            {
                // multiples below p * p were already crossed out by smaller primes
                for (int m = p * p; m <= n; m = m + p)
                {
                    composite[m] = true;
                }
            }
        }
    }

    /**
     * Counts the numbers from 2 to n that are not crossed out.
     * @return the number of primes up to n
     */
    int countPrimes()
    {
        count = 0;
        for (int i = 2; i <= n; i++)
        {
            if (!composite[i])
            {
                count++;
            }
        }
        return count;
    }

    /** Prints the primes up to n, then their count. */
    void display()
    {
        System.out.println("Prime numbers up to " + n + ":");
        for (int i = 2; i <= n; i++)
        {
            if (!composite[i])
            {
                System.out.print(i + " ");
            }
        }
        System.out.println();
        System.out.println("Count of primes = " + countPrimes());
    }

    /** Reads n, creates the object and calls the methods in order. */
    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 num = sc.nextInt();              // limit entered by the user
        Sieve ob = new Sieve(num);           // object holding the limit
        if (ob.isValid())
        {
            ob.crossOut();
            ob.display();
        }
        else
        {
            System.out.println("Invalid input. n must be from 2 to 1000.");
        }
    }
}

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: num = 30, so the constructor sets n = 30, count = 0. isValid() returns true.

display() prints the numbers from 2 to 30 that are not crossed out: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. countPrimes() finds 10 of them, so the last line is Count of primes = 10. This matches 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 up to n."
3. Largest prime "Find the largest prime not more than n using the sieve."