September 15, 2021

Sieve of Eratosthenes Algorithm

Kulwinder Kaurkulwinder3213

DURATION

10min

Definition

The sieve of Eratosthenes algorithm is an ancient algorithm that is used to find all the prime numbers less than given number T. It can be done using O(n*log(log(n))) operations. Using this algorithm we can eliminate all the numbers which are not prime and those that are less than given T. Also, we will traverse from 2 to the root of the given number ( √T ).

Reason for Traversing Until ( √T )

There will not exist any factor of T greater than ( √T ). Suppose x and y are the factors of T. In that case, x*y = T . Hence, at least one or both should be <=√ T, so we need to traverse until ( <=√ T ) only.

Regular Method

Finding all prime numbers using brute force will required O(n3 )

Pseudo Code

method 1: allPrimeBruteForce(T)

1
2
3
      for i = 2 to T
      if isPrime(i) print(i)
      End

method 2: isPrime( n )

1
2
3
4
     for i = 2 to n / 2
     if (n % i == 0) return true
     End
     return false;

Steps to Perform Sieve of Eratosthenes:

Generate numbers from 2 to T (2 is the smallest prime).
Traverse from smallest prime number which is num = 2.
Eliminate or mark all the multiples of num (as 0 or -1) which are lesser than or equal to T. It will help remove non-prime numbers and will help to reduce our number of comparisons to check for each number.
Update the value of num to the immediate next prime number. The next prime is the next (non 0 or -1) number in the list which is greater than the current number (num).
Repeat step three until num<=√T.
Traverse the whole list and number print. All the numbers (>=0) will be our required prime numbers lesser than T (given number).

Example

Print all prime numbers less than 15.

Create list = 2,3,4,5,6,7,8,9,10,11,12,13,14,15
num=2.
traverse from 2 to √15.
num =2. Remove all multiples of 2 then list= [ 2,3,0,5,0,7,0,9,0,11,0,13,0,15 ]
num=3, immediate non zero number.
Mark all multiples of 3 then list= [ 2,3,0,5,0,7,0,0,0,11,0,13,0,0 ]
num=5, which is the next prime, but num is not <=√15.

Now we have generated all the prime numbers less than 15. Prime numbers less than 15 are 2, 3, 5, 7, 11, 13.

Pseudo Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
boolean list = {
  2 to T
}
for i = 2 to <= √T
if (list[i])
  then {
    for j = i to j * i < N
    list[j * i] = false // Eliminate the multiple of i
  }
End
//To print Primes
for i = 2 to T
if (list[i])
  print(i + 1)
End

Java Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
  public static void printPrimes(int n) {

    if (n <= 2) return;
    boolean prime[] = new boolean[n];

    Arrays.fill(prime, true);

    for (int i = 2; i * i < n; i++) {
      if (prime[i]) {

        for (int j = i; j * i < n; j++) {
          prime[j * i] = false;
        }

      }
    }

    int count = 0;
    for (int i = 2; i < n; i++) {
      if (prime[i])
        System.out.print(i + "  ");
      count++;
      if (count % 10 == 0)
        System.out.println();
    }
  }
  public static void main(String args[]) {
    printPrimes(100);
  }
}