Sieve of Eratosthenes in 0(n) time complexity ❤️

The classical Sieve of Eratosthenes algorithm takes O(N log (log N)) time to find all prime numbers less than N. In this article, a modified Sieve is discussed that works in O(N) time.
Example :

Given a number N, print all prime 
numbers smaller than N

Input :  int N = 15
Output : 2 3 5 7 11 13

Input : int N = 20
Output : 2 3 5 7 11 13 17 19

Manipulated Sieve of Eratosthenes algorithm works as follows:

For every number i where i varies from 2 to N-1:
    Check if the number is prime. If the number
    is prime, store it in prime array.

For every prime numbers j less than or equal to the smallest  
prime factor p of i:
    Mark all numbers i*p as non_prime.
    Mark smallest prime factor of i*p as j

Below is the implementation of the above idea.

C++

// C++ program to generate all prime numbers
// less than N in O(N)
#include<bits/stdc++.h>
using namespace std;
const long long MAX_SIZE = 1000001;
 
// isPrime[] : isPrime[i] is true if number is prime 
// prime[] : stores all prime number less than N
// SPF[] that store smallest prime factor of number
// [for Exp : smallest prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
vector<long long >isprime(MAX_SIZE , true);
vector<long long >prime;
vector<long long >SPF(MAX_SIZE);
 
// function generate all prime number less than N in O(n)
void manipulated_seive(int N)
{
    // 0 and 1 are not prime
    isprime[0] = isprime[1] = false ;
 
    // Fill rest of the entries
    for (long long int i=2; i<N ; i++)
    {
        // If isPrime[i] == True then i is
        // prime number
        if (isprime[i])
        {
            // put i into prime[] vector
            prime.push_back(i);
 
            // A prime number is its own smallest
            // prime factor
            SPF[i] = i;
        }
 
        // Remove all multiples of  i*prime[j] which are
        // not prime by making isPrime[i*prime[j]] = false
        // and put smallest prime factor of i*Prime[j] as prime[j]
        // [ for exp :let  i = 5 , j = 0 , prime[j] = 2 [ i*prime[j] = 10 ]
        // so smallest prime factor of '10' is '2' that is prime[j] ]
        // this loop run only one time for number which are not prime
        for (long long int j=0;
             j < (int)prime.size() &&
             i*prime[j] < N && prime[j] <= SPF[i];
             j++)
        {
            isprime[i*prime[j]]=false;
 
            // put smallest prime factor of i*prime[j]
            SPF[i*prime[j]] = prime[j] ;
        }
    }
}
 
// driver  program to test above function
int main()
{
    int N = 13 ; // Must be less than MAX_SIZE
 
    manipulated_seive(N);
 
    // print all prime number less than N
    for (int i=0; i<prime.size() && prime[i] <= N ; i++)
        cout << prime[i] << " ";
 
    return 0;
}

Java

// Java program to generate all prime numbers
// less than N in O(N)
 
 
import java.util.Vector;
 
class Test
{
    static final int MAX_SIZE = 1000001;
    // isPrime[] : isPrime[i] is true if number is prime 
    // prime[] : stores all prime number less than N
    // SPF[] that store smallest prime factor of number
    // [for Exp : smallest prime factor of '8' and '16'
    // is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
    static Vector<Boolean>isprime = new Vector<>(MAX_SIZE);
    static Vector<Integer>prime = new Vector<>();
    static Vector<Integer>SPF = new Vector<>(MAX_SIZE);
      
    // method generate all prime number less than N in O(n)
    static void manipulated_seive(int N)
    {
        // 0 and 1 are not prime
        isprime.set(0, false);
        isprime.set(1, false);
         
        // Fill rest of the entries
        for (int i=2; i<N ; i++)
        {
            // If isPrime[i] == True then i is
            // prime number
            if (isprime.get(i))
            {
                // put i into prime[] vector
                prime.add(i);
      
                // A prime number is its own smallest
                // prime factor
                SPF.set(i,i);
            }
      
            // Remove all multiples of  i*prime[j] which are
            // not prime by making isPrime[i*prime[j]] = false
            // and put smallest prime factor of i*Prime[j] as prime[j]
            // [for exp :let  i = 5, j = 0, prime[j] = 2 [ i*prime[j] = 10]
            // so smallest prime factor of '10' is '2' that is prime[j] ]
            // this loop run only one time for number which are not prime
            for (int j=0;
                 j < prime.size() &&
                 i*prime.get(j) < N && prime.get(j) <= SPF.get(i);
                 j++)
            {
                isprime.set(i*prime.get(j),false);
      
                // put smallest prime factor of i*prime[j]
                SPF.set(i*prime.get(j),prime.get(j)) ;
            }
        }
    }
     
    // Driver method
    public static void main(String args[]) 
    {
        int N = 13 ; // Must be less than MAX_SIZE
         
        // initializing isprime and spf
        for (int i = 0; i < MAX_SIZE; i++){
            isprime.add(true);
            SPF.add(2);
        }
 
         
        manipulated_seive(N);
      
        // print all prime number less than N
        for (int i=0; i<prime.size() && prime.get(i) <= N ; i++)
            System.out.print(prime.get(i) + " ");
    }
}

Python3

# Python3 program to generate all 
# prime numbers less than N in O(N) 
 
MAX_SIZE = 1000001
 
# isPrime[] : isPrime[i] is true if
#             number is prime 
# prime[] : stores all prime number 
#           less than N 
# SPF[] that store smallest prime 
# factor of number [for ex : smallest 
# prime factor of '8' and '16' 
# is '2' so we put SPF[8] = 2 , 
# SPF[16] = 2 ] 
isprime = [True] * MAX_SIZE 
prime = [] 
SPF = [None] * (MAX_SIZE) 
 
# function generate all prime number 
# less than N in O(n) 
def manipulated_seive(N): 
 
    # 0 and 1 are not prime 
    isprime[0] = isprime[1] = False
 
    # Fill rest of the entries 
    for i in range(2, N): 
     
        # If isPrime[i] == True then i is 
        # prime number 
        if isprime[i] == True: 
         
            # put i into prime[] vector 
            prime.append(i) 
 
            # A prime number is its own smallest 
            # prime factor 
            SPF[i] = i 
         
        # Remove all multiples of i*prime[j] 
        # which are not prime by making is
        # Prime[i * prime[j]] = false and put
        # smallest prime factor of i*Prime[j]
        # as prime[j] [ for exp :let i = 5 , j = 0 ,
        # prime[j] = 2 [ i*prime[j] = 10 ] 
        # so smallest prime factor of '10' is '2' 
        # that is prime[j] ] this loop run only one 
        # time for number which are not prime 
        j = 0
        while (j < len(prime) and
               i * prime[j] < N and
                   prime[j] <= SPF[i]):
         
            isprime[i * prime[j]] = False
 
            # put smallest prime factor of i*prime[j] 
            SPF[i * prime[j]] = prime[j]
             
            j += 1
         
# Driver Code
if __name__ == "__main__": 
 
    N = 13 # Must be less than MAX_SIZE 
 
    manipulated_seive(N) 
 
    # print all prime number less than N 
    i = 0
    while i < len(prime) and prime[i] <= N:
        print(prime[i], end = " ") 
        i += 1
         
# This code is contributed by Rituraj Jain

C#

// C# program to generate all prime numbers
// less than N in O(N)
using System;
using System.Collections.Generic;
 
class Test {
  static int MAX_SIZE = 1000001;
 
  // isPrime[] : isPrime[i] is true if number is prime
  // prime[] : stores all prime number less than N
  // SPF[] that store smallest prime factor of number
  // [for Exp : smallest prime factor of '8' and '16'
  // is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
  static List<bool> isprime = new List<bool>(MAX_SIZE);
  static List<int> prime = new List<int>();
  static List<int> SPF = new List<int>(MAX_SIZE);
 
  // method generate all prime number less than N in O(n)
  static void manipulated_seive(int N)
  {
    // 0 and 1 are not prime
    isprime[0] = false;
    isprime[1] = false;
 
    // Fill rest of the entries
    for (int i = 2; i < N; i++)
    {
 
      // If isPrime[i] == True then i is
      // prime number
      if (isprime[i])
      {
 
        // put i into prime[] vector
        prime.Add(i);
 
        // A prime number is its own smallest
        // prime factor
        SPF[i] = i;
      }
 
      // Remove all multiples of  i*prime[j] which are
      // not prime by making isPrime[i*prime[j]] =
      // false and put smallest prime factor of
      // i*Prime[j] as prime[j] [for exp :let  i = 5,
      // j = 0, prime[j] = 2 [ i*prime[j] = 10] so
      // smallest prime factor of '10' is '2' that is
      // prime[j] ] this loop run only one time for
      // number which are not prime
      for (int j = 0;
           j < prime.Count && i * prime[j] < N
           && prime[j] <= SPF[i];
           j++) {
        isprime[i * prime[j]] = false;
 
        // put smallest prime factor of i*prime[j]
        SPF[i * prime[j]] = prime[j];
      }
    }
  }
 
  // Driver method
  public static void Main(string[] args)
  {
    int N = 13; // Must be less than MAX_SIZE
 
    // initializing isprime and spf
    for (int i = 0; i < MAX_SIZE; i++) {
      isprime.Add(true);
      SPF.Add(2);
    }
 
    manipulated_seive(N);
 
    // print all prime number less than N
    for (int i = 0; i < prime.Count && prime[i] <= N;
         i++)
      Console.Write(prime[i] + " ");
  }
}
 
// This code is contributed by phasing17

PHP

<?php
// PHP program to generate all 
// prime numbers less than N in O(N) 
 
$MAX_SIZE = 10001;
 
// isPrime[] : isPrime[i] is true if
//               number is prime 
// prime[] : stores all prime number 
//             less than N 
// SPF[] that store smallest prime 
// factor of number [for ex : smallest 
// prime factor of '8' and '16' 
// is '2' so we put SPF[8] = 2 , 
// SPF[16] = 2 ] 
$isprime = array_fill(0, $MAX_SIZE, true); 
$prime = array(); 
$SPF = array_fill(0, $MAX_SIZE, 0); 
 
// function generate all prime number 
// less than N in O(n) 
function manipulated_seive($N) 
{
    global $isprime, $MAX_SIZE,
                     $SPF, $prime;
     
    // 0 and 1 are not prime 
    $isprime[0] = $isprime[1] = false;
 
    // Fill rest of the entries 
    for ($i = 2; $i < $N; $i++)
    { 
     
        // If isPrime[i] == True then 
        // i is prime number 
        if ($isprime[$i]) 
        {
         
            // put i into prime[] vector 
            array_push($prime, $i); 
 
            // A prime number is its own  
            // smallest prime factor 
            $SPF[$i] = $i;
        }
         
        // Remove all multiples of i*prime[j] 
        // which are not prime by making is
        // Prime[i * prime[j]] = false and put
        // smallest prime factor of i*Prime[j]
        // as prime[j] [ for exp :let i = 5 , j = 0 ,
        // prime[j] = 2 [ i*prime[j] = 10 ] 
        // so smallest prime factor of '10' is '2' 
        // that is prime[j] ] this loop run only  
        // one time for number which are not prime 
        $j = 0;
        while ($j < count($prime) &&
               $i * $prime[$j] < $N &&
               $prime[$j] <= $SPF[$i])
       {
            $isprime[$i * $prime[$j]] = false;
 
            // put smallest prime factor of i*prime[j] 
            $SPF[$i * $prime[$j]] = $prime[$j];
             
            $j += 1;
        }
    }
}
         
// Driver Code
$N = 13; // Must be less than MAX_SIZE 
 
manipulated_seive($N); 
 
// print all prime number less than N 
$i = 0;
while ($i < count($prime) && 
       $prime[$i] <= $N)
{
    print($prime[$i] . " "); 
    $i += 1;
}
     
// This code is contributed by mits
?>

Javascript

<script>
 
  // Javascript program to generate all
  // prime numbers smaller than N in O(N)
 
  const MAX_SIZE = 1000001;
 
  // isPrime[] : isPrime[i] is true if the number is prime
  // prime[] : stores all prime numbers less than N
  // SPF[] that store smallest prime factor of number
  // [for Exp : smallest prime factor of '8' and '16'
  // is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
  var isPrime = Array.from({ length: MAX_SIZE }, (_, i) => true);
  var prime = [];
  var SPF = Array.from({ length: MAX_SIZE });
 
  // function that generates all prime number
  // less than N in O(N)
  function manipulated_sieve(N) {
   
    // 0 and 1 are not prime
    isPrime[0] = isPrime[1] = true;
 
    // Fill rest of the entries
    for (let i = 2; i < N; i++)
    {
      // If isPrime[i] === true, 
      // then i is a prime number
      if (isPrime[i])
      {
        // put i into prime[] array
        prime.push(i);
 
        // A prime number is its own smallest
        // prime factor
        SPF[i] = i;
      }
 
      // Remove all multiples of  i*prime[j] which are
      // not prime by making isPrime[i*prime[j]] = false
      // and put smallest prime factor of i*Prime[j] as prime[j]
      // [ for exp :let  i = 5 , j = 0 , prime[j] = 2 [ i*prime[j] = 10 ]
      // so smallest prime factor of '10' is '2' that is prime[j] ]
      // this loop run only one time for number which are not prime
      for (
        let j = 0;
        j < prime.length && i * prime[j] < N && prime[j] <= SPF[i];
        j++
      ) {
        isPrime[i * prime[j]] = false;
 
        // put smallest prime factor of i*prime[j]
        SPF[i * prime[j]] = prime[j];
      }
    }
  }
 
  // Driver Code
  var N = 13; // Must be less than MAX_SIZE
 
  manipulated_sieve(N);
   
  // print all prime numbers less than N
  for (let i = 0; i < prime.length && prime[i] <= N; i++) {
    document.write(prime[i] + " ");
  }
</script>

Output :

2 3 5 7 11

Auxiliary Space: O(1)
Illustration:

isPrime[0] = isPrime[1] = 0

After i = 2 iteration :
isPrime[]   [F, F, T, T, F, T, T, T] 
SPF[]       [0, 0, 2, 0, 2, 0, 0, 0]
     index   0  1  2  3  4  5  6  7

After i = 3 iteration :
isPrime[]  [F, F, T, T, F, T, F, T, T, F ]
SPF[]      [0, 0, 2, 3, 2, 0, 2, 0, 0, 3 ]
  index     0  1  2  3  4  5  6  7  8  9

After i = 4 iteration :
isPrime[]  [F, F, T, T, F, T, F, T, F, F]
SPF[]      [0, 0, 2, 3, 2, 0, 2, 0, 2, 3]
  index     0  1  2  3  4  5  6  7  8  9

Sieve of Eratosthenes in 0(n) time complexity

C++

Java

Python3

C#

PHP

Javascript

Contact Us