Posted on by Kalkicode
Code Mathematics

Sieve of eratosthenes

The Sieve of Eratosthenes is a classic algorithm for finding all prime numbers up to a given limit. It works by iteratively marking the multiples of each prime number starting from 2, effectively eliminating the composite numbers and leaving only the prime numbers. This article presents a C program that implements the Sieve of Eratosthenes algorithm to find and print prime numbers within a given range.

Problem Statement

Given a positive integer 'n', the task is to find and print all prime numbers that are less than or equal to 'n' using the Sieve of Eratosthenes algorithm.

Example

For instance, if 'n' is 25, the prime numbers in the range from 2 to 25 are 2, 3, 5, 7, 11, 13, 17, 19, and 23. Similarly, for 'n' as 100, the prime numbers are 2, 3, 5, 7, 11, 13, ..., 97. For 'n' as 200, the prime numbers are 2, 3, 5, 7, 11, 13, ..., 199.

Idea to Solve

The Sieve of Eratosthenes algorithm works by iteratively marking the multiples of each prime number and identifying the remaining unmarked numbers as prime. It starts with an array of integers representing whether a number is prime or not. By eliminating the multiples of each prime number, the algorithm eventually identifies the prime numbers within a given range.

Pseudocode

function sieve_of_eratosthenes(n):
        if n <= 1:
            Return
        Create an array 'prime' of size (n + 1) and initialize all elements to 1
        Set prime[0] and prime[1] as 0 (since 0 and 1 are not prime)
        Loop from i = 2 to sqrt(n):
            If prime[i] is 1:
                For j = i * i, j <= n, j += i:
                    Set prime[j] as 0 (mark multiples of prime[i] as not prime)
        Print "All prime of (2 -", n, ") is :"
        Print "[", prime elements marked as 1, "]"
    
    function main():
        sieve_of_eratosthenes(25)
        sieve_of_eratosthenes(100)
        sieve_of_eratosthenes(200)

Algorithm Explanation

  1. The sieve_of_eratosthenes function takes one parameter: 'n'.
  2. It checks if 'n' is less than or equal to 1, and if so, returns without performing any calculations.
  3. It creates an array 'prime' of size (n + 1) to track whether a number is prime or not.
  4. It initializes all elements of the 'prime' array to 1.
  5. It sets prime[0] and prime[1] as 0, since 0 and 1 are not prime.
  6. It loops from 'i' = 2 to sqrt(n) and checks if prime[i] is 1.
  7. If prime[i] is 1, it marks all multiples of 'i' as not prime by setting prime[j] to 0.
  8. It prints the prime elements (marked as 1) within the range (2 - n).
  9. The main function tests the sieve_of_eratosthenes function with different values.

Code Solution

// C Program
// Print prime number by using
// Sieve of eratosthenes
#include <stdio.h>

//Find all prime numbers which have smaller and equal to given number n
void sieve_of_eratosthenes(int n)
{
    if (n <= 1)
    {
        //When n are invalid to prime number 
        return;
    }
    //this are used to detect prime numbers
    int prime[n + 1];
    // Loop controlling variables
    int i;
    int j;
    // Initial two numbers are not prime (0 and 1)
    prime[0] = 0;
    prime[1] = 0;
    // Set the initial (2 to n element is prime)
    for (i = 2; i <= n; ++i)
    {
        prime[i] = 1;
    }
    // Initial 0 and 1 are not prime
    // We start to 2
    for (i = 2; i * i <= n; ++i)
    {
        if (prime[i] == 1)
        {
            //When i is prime number
            //Modify the prime status of all next multiplier of location i
            for (j = i * i; j <= n; j += i)
            {
                prime[j] = 0;
            }
        }
    }
    printf("\n All prime of (2 - %d) is :  \n [", n);
    //Display prime element
    for (i = 0; i <= n; ++i)
    {
        if (prime[i] == 1)
        {
            printf("  %d", i);
        }
    }
    printf("  ]\n");
}
int main()
{
    //Test Case
    sieve_of_eratosthenes(25);
    sieve_of_eratosthenes(100);
    sieve_of_eratosthenes(200);
    return 0;
}

Output

 All prime of (2 - 25) is :
 [  2  3  5  7  11  13  17  19  23  ]

 All prime of (2 - 100) is :
 [  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  ]

 All prime of (2 - 200) is :
 [  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  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199  ]
// Java Program
// Print prime number by using
// Sieve of eratosthenes
public class SieveOfEratosthenes
{
    //Find all prime numbers which have smaller and equal to given number n
    public void sieve_of_eratosthenes(int n)
    {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        //this are used to detect prime numbers
        boolean[] prime = new boolean[n + 1];
        // Loop controlling variables
        int i;
        int j;
        // Initial two numbers are not prime (0 and 1)
        prime[0] = false;
        prime[1] = false;
        // Set the initial (2 to n element is prime)
        for (i = 2; i <= n; ++i)
        {
            prime[i] = true;
        }
        // Initial 0 and 1 are not prime
        // We start to 2
        for (i = 2; i * i <= n; ++i)
        {
            if (prime[i] == true)
            {
                //When i is prime number
                //Modify the prime status of all next multiplier of location i
                for (j = i * i; j <= n; j += i)
                {
                    prime[j] = false;
                }
            }
        }
        System.out.print("\n All prime of (2 - " + n + ") is : \n [");
        //Display prime element
        for (i = 0; i <= n; ++i)
        {
            if (prime[i] == true)
            {
                System.out.print("  " + i);
            }
        }
        System.out.print(" ]\n");
    }
    public static void main(String[] args)
    {
        SieveOfEratosthenes obj = new SieveOfEratosthenes();
        //Test Case
        obj.sieve_of_eratosthenes(25);
        obj.sieve_of_eratosthenes(100);
        obj.sieve_of_eratosthenes(200);
    }
}

Output

 All prime of (2 - 25) is :
 [  2  3  5  7  11  13  17  19  23 ]

 All prime of (2 - 100) is :
 [  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 ]

 All prime of (2 - 200) is :
 [  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  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]
//Include header file
#include <iostream>
using namespace std;

// C++ Program
// Print prime number by using
// Sieve of eratosthenes

class SieveOfEratosthenes
{
    public:
        //Find all prime numbers which have smaller and equal to given number n
        void sieve_of_eratosthenes(int n)
        {
            if (n <= 1)
            {
                //When n are invalid to prime number 
                return;
            }
            //this are used to detect prime numbers
            bool prime[n + 1];
            // Loop controlling variables
            int i;
            int j;
            // Initial two numbers are not prime (0 and 1)
            prime[0] = false;
            prime[1] = false;
            // Set the initial (2 to n element is prime)
            for (i = 2; i <= n; ++i)
            {
                prime[i] = true;
            }
            // Initial 0 and 1 are not prime
            // We start to 2
            for (i = 2; i *i <= n; ++i)
            {
                if (prime[i] == true)
                {
                    //When i is prime number
                    //Modify the prime status of all next multiplier of location i
                    for (j = i *i; j <= n; j += i)
                    {
                        prime[j] = false;
                    }
                }
            }
            cout << "\n All prime of (2 - " << n << ") is : \n [";
            //Display prime element
            for (i = 0; i <= n; ++i)
            {
                if (prime[i] == true)
                {
                    cout << "  " << i;
                }
            }
            cout << " ]\n";
        }
};
int main()
{
    SieveOfEratosthenes obj = SieveOfEratosthenes();
    //Test Case
    obj.sieve_of_eratosthenes(25);
    obj.sieve_of_eratosthenes(100);
    obj.sieve_of_eratosthenes(200);
    return 0;
}

Output

 All prime of (2 - 25) is :
 [  2  3  5  7  11  13  17  19  23 ]

 All prime of (2 - 100) is :
 [  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 ]

 All prime of (2 - 200) is :
 [  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  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]
//Include namespace system
using System;

// C# Program
// Print prime number by using
// Sieve of eratosthenes

public class SieveOfEratosthenes
{
    //Find all prime numbers which have smaller and equal to given number n
    public void sieve_of_eratosthenes(int n)
    {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        //this are used to detect prime numbers
        Boolean[] prime = new Boolean[n + 1];
        // Loop controlling variables
        int i;
        int j;
        // Initial two numbers are not prime (0 and 1)
        prime[0] = false;
        prime[1] = false;
        // Set the initial (2 to n element is prime)
        for (i = 2; i <= n; ++i)
        {
            prime[i] = true;
        }
        // Initial 0 and 1 are not prime
        // We start to 2
        for (i = 2; i * i <= n; ++i)
        {
            if (prime[i] == true)
            {
                //When i is prime number
                //Modify the prime status of all next multiplier of location i
                for (j = i * i; j <= n; j += i)
                {
                    prime[j] = false;
                }
            }
        }
        Console.Write("\n All prime of (2 - " + n + ") is : \n [");
        //Display prime element
        for (i = 0; i <= n; ++i)
        {
            if (prime[i] == true)
            {
                Console.Write("  " + i);
            }
        }
        Console.Write(" ]\n");
    }
    public static void Main(String[] args)
    {
        SieveOfEratosthenes obj = new SieveOfEratosthenes();
        //Test Case
        obj.sieve_of_eratosthenes(25);
        obj.sieve_of_eratosthenes(100);
        obj.sieve_of_eratosthenes(200);
    }
}

Output

 All prime of (2 - 25) is :
 [  2  3  5  7  11  13  17  19  23 ]

 All prime of (2 - 100) is :
 [  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 ]

 All prime of (2 - 200) is :
 [  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  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]
<?php
// Php Program
// Print prime number by using
// Sieve of eratosthenes
class SieveOfEratosthenes
{
    //Find all prime numbers which have smaller and equal to given number n
    public  function sieve_of_eratosthenes($n)
    {
        if ($n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        // This are used to detect prime numbers
        // Set the n all numbers is prime
        $prime = array_fill(0, $n + 1, true);
        // Loop controlling variables
        $i = 0;
        $j = 0;
        // Initial two numbers are not prime (0 and 1)
        $prime[0] = false;
        $prime[1] = false;
        
        // Initial 0 and 1 are not prime
        // We start to 2
        for ($i = 2; $i * $i <= $n; ++$i)
        {
            if ($prime[$i] == true)
            {
                //When i is prime number
                //Modify the prime status of all next multiplier of location i
                for ($j = $i * $i; $j <= $n; $j += $i)
                {
                    $prime[$j] = false;
                }
            }
        }
        echo "\n All prime of (2 - ". $n .") is : \n [";
        //Display prime element
        for ($i = 0; $i <= $n; ++$i)
        {
            if ($prime[$i] == true)
            {
                echo "  ". $i;
            }
        }
        echo " ]\n";
    }
}

function main()
{
    $obj = new SieveOfEratosthenes();
    //Test Case
    $obj->sieve_of_eratosthenes(25);
    $obj->sieve_of_eratosthenes(100);
    $obj->sieve_of_eratosthenes(200);
}
main();

Output

 All prime of (2 - 25) is :
 [  2  3  5  7  11  13  17  19  23 ]

 All prime of (2 - 100) is :
 [  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 ]

 All prime of (2 - 200) is :
 [  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  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]
// Node Js Program
// Print prime number by using
// Sieve of eratosthenes
class SieveOfEratosthenes
{
    //Find all prime numbers which have smaller and equal to given number n
    sieve_of_eratosthenes(n)
    {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        // This are used to detect prime numbers
        // Set the n all numbers is prime
        var prime = Array(n + 1).fill(true);
        // Loop controlling variables
        var i = 0;
        var j = 0;
        // Initial two numbers are not prime (0 and 1)
        prime[0] = false;
        prime[1] = false;
    
        // Initial 0 and 1 are not prime
        // We start to 2
        for (i = 2; i * i <= n; ++i)
        {
            if (prime[i] == true)
            {
                //When i is prime number
                //Modify the prime status of all next multiplier of location i
                for (j = i * i; j <= n; j += i)
                {
                    prime[j] = false;
                }
            }
        }
        process.stdout.write("\n All prime of (2 - " + n + ") is : \n [");
        //Display prime element
        for (i = 0; i <= n; ++i)
        {
            if (prime[i] == true)
            {
                process.stdout.write("  " + i);
            }
        }
        process.stdout.write(" ]\n");
    }
}

function main()
{
    var obj = new SieveOfEratosthenes();
    //Test Case
    obj.sieve_of_eratosthenes(25);
    obj.sieve_of_eratosthenes(100);
    obj.sieve_of_eratosthenes(200);
}
main();

Output

 All prime of (2 - 25) is :
 [  2  3  5  7  11  13  17  19  23 ]

 All prime of (2 - 100) is :
 [  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 ]

 All prime of (2 - 200) is :
 [  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  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]
#  Python 3 Program
#  Print prime number by using
#  Sieve of eratosthenes
class SieveOfEratosthenes :
    # Find all prime numbers which have smaller and equal to given number n
    def sieve_of_eratosthenes(self, n) :
        if (n <= 1) :
            # When n are invalid to prime number 
            return
        
        #  This are used to detect prime numbers
        #  Set the n all numbers is prime
        prime = [True] * (n + 1)
        #  Loop controlling variables
        i = 0
        j = 0
        #  Initial two numbers are not prime (0 and 1)
        prime[0] = False
        prime[1] = False

        #  We start to 2
        i = 2
        while (i * i <= n) :
            if (prime[i] == True) :
                # When i is prime number
                # Modify the prime status of all next multiplier of location i
                j = i * i
                while (j <= n) :
                    prime[j] = False
                    j += i
                
            
            i += 1
        
        print("\n All prime of (2 - ", n ,") is : \n [", end = "")
        # Display prime element
        i = 0
        while (i <= n) :
            if (prime[i] == True) :
                print("  ", i, end = "")
            
            i += 1
        
        print(" ]\n", end = "")
    

def main() :
    obj = SieveOfEratosthenes()
    # Test Case
    obj.sieve_of_eratosthenes(25)
    obj.sieve_of_eratosthenes(100)
    obj.sieve_of_eratosthenes(200)

if __name__ == "__main__": main()

Output

 All prime of (2 -  25 ) is :
 [   2   3   5   7   11   13   17   19   23 ]

 All prime of (2 -  100 ) is :
 [   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 ]

 All prime of (2 -  200 ) is :
 [   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   101   103   107   109   113   127   131   137   139   149   151   157   163   167   173   179   181   191   193   197   199 ]
#  Ruby Program
#  Print prime number by using
#  Sieve of eratosthenes
class SieveOfEratosthenes

    # Find all prime numbers which have smaller and equal to given number n
    def sieve_of_eratosthenes(n)
    
        if (n <= 1)
        
            # When n are invalid to prime number 
            return
        end
        #  This are used to detect prime numbers
        #  Set the n all numbers is prime
        prime = Array.new(n + 1) {true}
        #  Loop controlling variables
        i = 0
        j = 0
        #  Initial two numbers are not prime (0 and 1)
        prime[0] = false
        prime[1] = false
        #  We start to 2
        i = 2
        while (i * i <= n)
        
            if (prime[i] == true)
            
                # When i is prime number
                # Modify the prime status of all next multiplier of location i
                j = i * i
                while (j <= n)
                
                    prime[j] = false
                    j += i
                end
            end
            i += 1
        end
        print("\n All prime of (2 - ", n ,") is : \n [")
        # Display prime element
        i = 0
        while (i <= n)
        
            if (prime[i] == true)
            
                print("  ", i)
            end
            i += 1
        end
        print(" ]\n")
    end
end
def main()

    obj = SieveOfEratosthenes.new()
    # Test Case
    obj.sieve_of_eratosthenes(25)
    obj.sieve_of_eratosthenes(100)
    obj.sieve_of_eratosthenes(200)
end
main()

Output

 All prime of (2 - 25) is : 
 [  2  3  5  7  11  13  17  19  23 ]

 All prime of (2 - 100) is : 
 [  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 ]

 All prime of (2 - 200) is : 
 [  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  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]
// Scala Program
// Print prime number by using
// Sieve of eratosthenes
class SieveOfEratosthenes
{
    //Find all prime numbers which have smaller and equal to given number n
    def sieve_of_eratosthenes(n: Int): Unit = {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        // This are used to detect prime numbers
        // Set the n all numbers is prime
        var prime: Array[Boolean] = Array.fill[Boolean](n + 1)(true);
        // Loop controlling variables
        var i: Int = 0;
        var j: Int = 0;
        // Initial two numbers are not prime (0 and 1)
        prime(0) = false;
        prime(1) = false;
    
        // We start to 2
        i = 2;
        while (i * i <= n)
        {
            if (prime(i) == true)
            {
                //When i is prime number
                //Modify the prime status of all next multiplier of location i
                j = i * i;
                while (j <= n)
                {
                    prime(j) = false;
                    j += i;
                }
            }
            i += 1;
        }
        print("\n All prime of (2 - " + n + ") is : \n [");
        //Display prime element
        i = 0;
        while (i <= n)
        {
            if (prime(i) == true)
            {
                print("  " + i);
            }
            i += 1;
        }
        print(" ]\n");
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var obj: SieveOfEratosthenes = new SieveOfEratosthenes();
        //Test Case
        obj.sieve_of_eratosthenes(25);
        obj.sieve_of_eratosthenes(100);
        obj.sieve_of_eratosthenes(200);
    }
}

Output

 All prime of (2 - 25) is :
 [  2  3  5  7  11  13  17  19  23 ]

 All prime of (2 - 100) is :
 [  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 ]

 All prime of (2 - 200) is :
 [  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  101  103  107  109  113  127  131  137  139  149  151  157  163  167  173  179  181  191  193  197  199 ]
// Swift Program
// Print prime number by using
// Sieve of eratosthenes
class SieveOfEratosthenes
{
    //Find all prime numbers which have smaller and equal to given number n
    func sieve_of_eratosthenes(_ n: Int)
    {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        // This are used to detect prime numbers
        // Set the n all numbers is prime
        var prime: [Bool] = Array(repeating: true, count: n + 1);
        // Loop controlling variables
        var i: Int = 0;
        var j: Int = 0;
        // Initial two numbers are not prime (0 and 1)
        prime[0] = false;
        prime[1] = false;

        // We start to 2
        i = 2;
        while (i * i <= n)
        {
            if (prime[i] == true)
            {
                //When i is prime number
                //Modify the prime status of all next multiplier of location i
                j = i * i;
                while (j <= n)
                {
                    prime[j] = false;
                    j += i;
                }
            }
            i += 1;
        }
        print("\n All prime of (2 - ", n ,") is : \n [", terminator: "");
        //Display prime element
        i = 0;
        while (i <= n)
        {
            if (prime[i] == true)
            {
                print("  ", i, terminator: "");
            }
            i += 1;
        }
        print(" ]\n", terminator: "");
    }
}
func main()
{
    let obj: SieveOfEratosthenes = SieveOfEratosthenes();
    //Test Case
    obj.sieve_of_eratosthenes(25);
    obj.sieve_of_eratosthenes(100);
    obj.sieve_of_eratosthenes(200);
}
main();

Output

 All prime of (2 -  25 ) is :
 [   2   3   5   7   11   13   17   19   23 ]

 All prime of (2 -  100 ) is :
 [   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 ]

 All prime of (2 -  200 ) is :
 [   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   101   103   107   109   113   127   131   137   139   149   151   157   163   167   173   179   181   191   193   197   199 ]

Time Complexity

The time complexity of the Sieve of Eratosthenes algorithm is approximately O(n * log(log n)), which is very efficient compared to other methods of finding prime numbers. It involves marking each non-prime number only once and looping up to the square root of 'n'.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment