Skip to main content

Bitwise Sieve

The Bitwise Sieve is a variant of the Sieve of Eratosthenes, a classical algorithm used to find all prime numbers up to a given limit. The Bitwise Sieve optimizes the space usage by representing numbers using bits in an array, which significantly reduces the memory requirement compared to a traditional array.

Problem Statement

The problem is to efficiently find all prime numbers within a given range [2, n] using the Bitwise Sieve algorithm.

Example

Let's take an example with n = 25.

  1. Initialize an array called sieve with bits, where each bit corresponds to a number. A set bit indicates the number is composite (not prime), and a clear bit indicates the number is prime.
  2. Start with the first prime number, 2.
  3. For each prime number p, mark all multiples of p as composite starting from p * p, as all smaller multiples would have been marked by previous primes.
  4. Repeat this process for all primes less than or equal to the square root of n.

Idea to Solve

The Bitwise Sieve algorithm aims to eliminate memory overhead by representing numbers as bits in an array. Instead of using an array where each element represents a number, the algorithm uses a bit array where each bit represents a number. This way, the memory required is greatly reduced, especially when working with large ranges.

Pseudocode

function non_prime(num, position):
    return (num & (1 << position))

function update_status(num, position):
    return (num | (1 << position))

function bitwise_sieve(n):
    if n <= 1:
        return

    space = (n >> 5) + 2
    sieve[space]

    for i = 3 to sqrt(n) step 2:
        slot = i >> 5
        position = i & 31
        if non_prime(sieve[slot], position) == 0:
            for j = i * i to n step (i << 1):
                slot = j >> 5
                position = j & 31
                sieve[slot] = update_status(sieve[slot], position)

    print("Prime numbers from 2 to", n)
    print("[ 2")
    for i = 3 to n step 2:
        slot = i >> 5
        position = i & 31
        if non_prime(sieve[slot], position) == 0:
            print(i)
    print("]")

Algorithm Explanation

  1. The algorithm defines two helper functions, non_prime and update_status, which operate on the bits in the sieve array.
  2. The bitwise_sieve function initializes the sieve array and iterates through odd numbers starting from 3 up to the square root of n.
  3. For each prime number found, it marks its multiples as non-prime in the sieve array.
  4. The algorithm then prints the prime numbers in the given range.

Code Solution

Here given code implementation process.

// C Program
// Print Prime numbers using
// Bitwise Sieve
#include <stdio.h>

int non_prime(int num, int position)
{
    return (num & (1 << position));
}
int update_status(int num, int position)
{
    return (num | (1 << position));
}
//Find all prime numbers which have smaller and equal to given number n
void bitwise_sieve(int n)
{
    if (n <= 1)
    {
        //When n are invalid to prime number 
        return;
    }
    int space = (n >> 5) + 2;
    //This are used to detect prime numbers
    int sieve[space];
    // Loop controlling variables
    int i = 0;
    int j = 0;
    //define some auxiliary variable
    int slot = 0;
    int position = 0;
    for (i = 3; i * i <= n; i = i + 2)
    {
        //get slot and position
        slot = i >> 5;
        position = i & 31;
        if (non_prime(sieve[slot], position) == 0)
        {
            for (j = i * i; j <= n; j += (i << 1))
            {
                //get slot and position
                slot = j >> 5;
                position = j & 31;
                sieve[slot] = update_status(sieve[slot], position);
            }
        }
    }
    printf("\n Prime of (2 - %d) are \n", n);
    //Display first element
    printf(" [ 2");
    for (i = 3; i <= n; i = i + 2)
    {
        //get slot and position
        slot = i >> 5;
        position = i & 31;
        if (non_prime(sieve[slot], position) == 0)
        {
            //When [i] is a prime number
            printf("  %d", i);
        }
    }
    printf(" ] \n");
}
int main()
{
    bitwise_sieve(25);
    bitwise_sieve(101);
    bitwise_sieve(200);
    return 0;
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 2  3  11  13  17  19  23  25  29  31  35  37  41  43  47  49  53  55  59  61  67  77  79  83  85  89  91  95  97  101 ]

 Prime of (2 - 200) are
 [ 2  3  11  13  17  19  23  25  29  31  35  37  41  43  47  49  53  55  59  61  67  77  79  83  85  89  91  95  97  101  103  107  109  113  115  119  125  127  131  139  145  151  157  163  175  181 ]
// Java Program
// Print prime number by using
// Bitwise Sieve
class BitwiseSieve
{
    public int non_prime(int num, int position)
    {
        return (num & (1 << position));
    }
    public int update_status(int num, int position)
    {
        return (num | (1 << position));
    }
    //Find all prime numbers which have smaller and equal to given number n
    public void bitwise_sieve(int n)
    {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        int space = (n >> 5) + 2;
        //This are used to detect prime numbers
        int[] sieve = new int[space];
        // Loop controlling variables
        int i = 0;
        int j = 0;
        //define some auxiliary variable
        int slot = 0;
        int position = 0;
        for (i = 3; i * i <= n; i = i + 2)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (non_prime(sieve[slot], position) == 0)
            {
                for (j = i * i; j <= n; j += (i << 1))
                {
                    //get slot and position
                    slot = j >> 5;
                    position = j & 31;
                    sieve[slot] = update_status(sieve[slot], position);
                }
            }
        }
        System.out.print("\n Prime of (2 - " + n + ") are \n");
        //Display first element
        System.out.print(" [ 2");
        for (i = 3; i <= n; i = i + 2)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (non_prime(sieve[slot], position) == 0)
            {
                //When [i] is a prime number
                System.out.print("  " + i);
            }
        }
        System.out.print(" ] \n");
    }
    public static void main(String[] args)
    {
        BitwiseSieve obj = new BitwiseSieve();
        //Test Case
        obj.bitwise_sieve(25);
        obj.bitwise_sieve(101);
        obj.bitwise_sieve(200);
    }
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
// Bitwise Sieve

class BitwiseSieve
{
    public: 
    int non_prime(int num, int position)
    {
        return (num & (1 << position));
    }
    int update_status(int num, int position)
    {
        return (num | (1 << position));
    }
    //Find all prime numbers which have smaller and equal to given number n
    void bitwise_sieve(int n)
    {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        int space = (n >> 5) + 2;
        //This are used to detect prime numbers
        int sieve[space];
        // Loop controlling variables
        int i = 0;
        int j = 0;
        //define some auxiliary variable
        int slot = 0;
        int position = 0;
        for (i = 3; i *i <= n; i = i + 2)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (this->non_prime(sieve[slot], position) == 0)
            {
                for (j = i *i; j <= n; j += (i << 1))
                {
                    //get slot and position
                    slot = j >> 5;
                    position = j & 31;
                    sieve[slot] = this->update_status(sieve[slot], position);
                }
            }
        }
        cout << "\n Prime of (2 - " << n << ") are \n";
        //Display first element
        cout << " [ 2";
        for (i = 3; i <= n; i = i + 2)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (this->non_prime(sieve[slot], position) == 0)
            {
                //When [i] is a prime number
                cout << "  " << i;
            }
        }
        cout << " ] \n";
    }
};
int main()
{
    BitwiseSieve obj = BitwiseSieve();
    //Test Case
    obj.bitwise_sieve(25);
    obj.bitwise_sieve(101);
    obj.bitwise_sieve(200);
    return 0;
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 2  3  7  11  13  23  29  47  53  55  59  61  67  71  79  83  85  89  95  97  101 ]

 Prime of (2 - 200) are
 [ 2  3  7  11  13  23  29  47  53  55  59  61  67  71  79  83  85  89  95  97  101  103  107  109  113  115  125  127  131  139  151  157  181  199 ]
//Include namespace system
using System;

// C# Program
// Print prime number by using
// Bitwise Sieve

class BitwiseSieve
{
    public int non_prime(int num, int position)
    {
        return (num & (1 << position));
    }
    public int update_status(int num, int position)
    {
        return (num | (1 << position));
    }
    //Find all prime numbers which have smaller and equal to given number n
    public void bitwise_sieve(int n)
    {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        int space = (n >> 5) + 2;
        //This are used to detect prime numbers
        int[] sieve = new int[space];
        // Loop controlling variables
        int i = 0;
        int j = 0;
        //define some auxiliary variable
        int slot = 0;
        int position = 0;
        for (i = 3; i * i <= n; i = i + 2)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (non_prime(sieve[slot], position) == 0)
            {
                for (j = i * i; j <= n; j += (i << 1))
                {
                    //get slot and position
                    slot = j >> 5;
                    position = j & 31;
                    sieve[slot] = update_status(sieve[slot], position);
                }
            }
        }
        Console.Write("\n Prime of (2 - " + n + ") are \n");
        //Display first element
        Console.Write(" [ 2");
        for (i = 3; i <= n; i = i + 2)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (non_prime(sieve[slot], position) == 0)
            {
                //When [i] is a prime number
                Console.Write("  " + i);
            }
        }
        Console.Write(" ] \n");
    }
    public static void Main(String[] args)
    {
        BitwiseSieve obj = new BitwiseSieve();
        //Test Case
        obj.bitwise_sieve(25);
        obj.bitwise_sieve(101);
        obj.bitwise_sieve(200);
    }
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
// Bitwise Sieve

class BitwiseSieve
{
    public  function non_prime($num, $position)
    {
        return ($num & (1 << $position));
    }
    public  function update_status($num, $position)
    {
        return ($num | (1 << $position));
    }
    //Find all prime numbers which have smaller and equal to given number n
    public  function bitwise_sieve($n)
    {
        if ($n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        $space = ($n >> 5) + 2;
        //This are used to detect prime numbers
        $sieve = array_fill(0, $space, 0);
        // Loop controlling variables
        $i = 0;
        $j = 0;
        //define some auxiliary variable
        $slot = 0;
        $position = 0;
        for ($i = 3; $i * $i <= $n; $i = $i + 2)
        {
            //get slot and position
            $slot = $i >> 5;
            $position = $i & 31;
            if ($this->non_prime($sieve[$slot], $position) == 0)
            {
                for ($j = $i * $i; $j <= $n; $j += ($i << 1))
                {
                    //get slot and position
                    $slot = $j >> 5;
                    $position = $j & 31;
                    $sieve[$slot] = $this->update_status($sieve[$slot], $position);
                }
            }
        }
        echo "\n Prime of (2 - ". $n .") are \n";
        //Display first element
        echo " [ 2";
        for ($i = 3; $i <= $n; $i = $i + 2)
        {
            //get slot and position
            $slot = $i >> 5;
            $position = $i & 31;
            if ($this->non_prime($sieve[$slot], $position) == 0)
            {
                //When [i] is a prime number
                echo "  ". $i;
            }
        }
        echo " ] \n";
    }
}

function main()
{
    $obj = new BitwiseSieve();
    //Test Case
    $obj->bitwise_sieve(25);
    $obj->bitwise_sieve(101);
    $obj->bitwise_sieve(200);
}
main();

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
// Bitwise Sieve

class BitwiseSieve
{
    non_prime(num, position)
    {
        return (num & (1 << position));
    }
    update_status(num, position)
    {
        return (num | (1 << position));
    }
    //Find all prime numbers which have smaller and equal to given number n
    bitwise_sieve(n)
    {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        var space = (n >> 5) + 2;
        //This are used to detect prime numbers
        var sieve = Array(space).fill(0);
        // Loop controlling variables
        var i = 0;
        var j = 0;
        //define some auxiliary variable
        var slot = 0;
        var position = 0;
        for (i = 3; i * i <= n; i = i + 2)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (this.non_prime(sieve[slot], position) == 0)
            {
                for (j = i * i; j <= n; j += (i << 1))
                {
                    //get slot and position
                    slot = j >> 5;
                    position = j & 31;
                    sieve[slot] = this.update_status(sieve[slot], position);
                }
            }
        }
        process.stdout.write("\n Prime of (2 - " + n + ") are \n");
        //Display first element
        process.stdout.write(" [ 2");
        for (i = 3; i <= n; i = i + 2)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (this.non_prime(sieve[slot], position) == 0)
            {
                //When [i] is a prime number
                process.stdout.write("  " + i);
            }
        }
        process.stdout.write(" ] \n");
    }
}

function main()
{
    var obj = new BitwiseSieve();
    //Test Case
    obj.bitwise_sieve(25);
    obj.bitwise_sieve(101);
    obj.bitwise_sieve(200);
}
main();

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
#  Bitwise Sieve

class BitwiseSieve :
    def non_prime(self, num, position) :
        return (num & (1 << position))
    
    def update_status(self, num, position) :
        return (num | (1 << position))
    
    # Find all prime numbers which have smaller and equal to given number n
    def bitwise_sieve(self, n) :
        if (n <= 1) :
            # When n are invalid to prime number 
            return
        
        space = (n >> 5) + 2
        # This are used to detect prime numbers
        sieve = [0] * space
        # define some auxiliary variable
        slot = 0
        position = 0
        #  Loop controlling variables
        i = 3
        j = 0
        while (i * i <= n) :
            # get slot and position
            slot = i >> 5
            position = i & 31
            if (self.non_prime(sieve[slot], position) == 0) :
                j = i * i
                while (j <= n) :
                    # get slot and position
                    slot = j >> 5
                    position = j & 31
                    sieve[slot] = self.update_status(sieve[slot], position)
                    j += (i << 1)
                
            
            i = i + 2
        
        print("\n Prime of (2 - ", n ,") are \n", end = "")
        # Display first element
        print(" [ 2", end = "")
        i = 3
        while (i <= n) :
            # get slot and position
            slot = i >> 5
            position = i & 31
            if (self.non_prime(sieve[slot], position) == 0) :
                # When [i] is a prime number
                print("  ", i, end = "")
            
            i = i + 2
        
        print(" ] \n", end = "")
    

def main() :
    obj = BitwiseSieve()
    # Test Case
    obj.bitwise_sieve(25)
    obj.bitwise_sieve(101)
    obj.bitwise_sieve(200)

if __name__ == "__main__": main()

Output

 Prime of (2 -  25 ) are
 [ 2   3   5   7   11   13   17   19   23 ]

 Prime of (2 -  101 ) are
 [ 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 ]

 Prime of (2 -  200 ) are
 [ 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
#  Bitwise Sieve
class BitwiseSieve

    def non_prime(num, position)
        return (num & (1 << position))
    end
    def update_status(num, position)
    
        return (num | (1 << position))
    end
    # Find all prime numbers which have smaller and equal to given number n
    def bitwise_sieve(n)
    
        if (n <= 1)
            # When n are invalid to prime number 
            return
        end
        space = (n >> 5) + 2
        # This are used to detect prime numbers
        sieve = Array.new(space) {0}
        # define some auxiliary variable
        slot = 0
        position = 0
        #  Loop controlling variables
        i = 3
        j = 0
        while (i * i <= n)
        
            # get slot and position
            slot = i >> 5
            position = i & 31
            if (self.non_prime(sieve[slot], position) == 0)
            
                j = i * i
                while (j <= n)
                
                    # get slot and position
                    slot = j >> 5
                    position = j & 31
                    sieve[slot] = self.update_status(sieve[slot], position)
                    j += (i << 1)
                end
            end
            i = i + 2
        end
        print("\n Prime of (2 - ", n ,") are \n")
        # Display first element
        print(" [ 2")
        i = 3
        while (i <= n)
        
            # get slot and position
            slot = i >> 5
            position = i & 31
            if (self.non_prime(sieve[slot], position) == 0)
            
                # When [i] is a prime number
                print("  ", i)
            end
            i = i + 2
        end
        print(" ] \n")
    end
end
def main()

    obj = BitwiseSieve.new()
    # Test Case
    obj.bitwise_sieve(25)
    obj.bitwise_sieve(101)
    obj.bitwise_sieve(200)
end
main()

Output

 Prime of (2 - 25) are 
 [ 2  3  5  7  11  13  17  19  23 ] 

 Prime of (2 - 101) are 
 [ 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 ] 

 Prime of (2 - 200) are 
 [ 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
// Bitwise Sieve
class BitwiseSieve
{
    def non_prime(num: Int, position: Int): Int = {
        return (num & (1 << position));
    }
    def update_status(num: Int, position: Int): Int = {
        return (num | (1 << position));
    }
    //Find all prime numbers which have smaller and equal to given number n
    def bitwise_sieve(n: Int): Unit = {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        var space: Int = (n >> 5) + 2;
        //This are used to detect prime numbers
        var sieve: Array[Int] = Array.fill[Int](space)(0);
        //define some auxiliary variable
        var slot: Int = 0;
        var position: Int = 0;
        // Loop controlling variables
        var i: Int = 3;
        var j: Int = 0;
        while (i * i <= n)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (non_prime(sieve(slot), position) == 0)
            {
                j = i * i;
                while (j <= n)
                {
                    //get slot and position
                    slot = j >> 5;
                    position = j & 31;
                    sieve(slot) = update_status(sieve(slot), position);
                    j += (i << 1);
                }
            }
            i = i + 2;
        }
        print("\n Prime of (2 - " + n + ") are \n");
        //Display first element
        print(" [ 2");
        i = 3;
        while (i <= n)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (non_prime(sieve(slot), position) == 0)
            {
                //When [i] is a prime number
                print("  " + i);
            }
            i = i + 2;
        }
        print(" ] \n");
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var obj: BitwiseSieve = new BitwiseSieve();
        //Test Case
        obj.bitwise_sieve(25);
        obj.bitwise_sieve(101);
        obj.bitwise_sieve(200);
    }
}

Output

 Prime of (2 - 25) are
 [ 2  3  5  7  11  13  17  19  23 ]

 Prime of (2 - 101) are
 [ 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 ]

 Prime of (2 - 200) are
 [ 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
// Bitwise Sieve
class BitwiseSieve
{
    func non_prime(_ num: Int, _ position: Int) -> Int
    {
        return (num & (1 << position));
    }
    func update_status(_ num: Int, _ position: Int) -> Int
    {
        return (num | (1 << position));
    }
    //Find all prime numbers which have smaller and equal to given number n
    func bitwise_sieve(_ n: Int)
    {
        if (n <= 1)
        {
            //When n are invalid to prime number 
            return;
        }
        let space: Int = (n >> 5) + 2;
        //This are used to detect prime numbers
        var sieve: [Int] = Array(repeating: 0, count: space);
        //define some auxiliary variable
        var slot: Int = 0;
        var position: Int = 0;
        // Loop controlling variables
        var i: Int = 3;
        var j: Int = 0;
        while (i * i <= n)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (self.non_prime(sieve[slot], position) == 0)
            {
                j = i * i;
                while (j <= n)
                {
                    //get slot and position
                    slot = j >> 5;
                    position = j & 31;
                    sieve[slot] = self.update_status(sieve[slot], position);
                    j += (i << 1);
                }
            }
            i = i + 2;
        }
        print("\n Prime of (2 - ", n ,") are \n", terminator: "");
        //Display first element
        print(" [ 2", terminator: "");
        i = 3;
        while (i <= n)
        {
            //get slot and position
            slot = i >> 5;
            position = i & 31;
            if (self.non_prime(sieve[slot], position) == 0)
            {
                //When [i] is a prime number
                print("  ", i, terminator: "");
            }
            i = i + 2;
        }
        print(" ] \n", terminator: "");
    }
}
func main()
{
    let obj: BitwiseSieve = BitwiseSieve();
    //Test Case
    obj.bitwise_sieve(25);
    obj.bitwise_sieve(101);
    obj.bitwise_sieve(200);
}
main();

Output

 Prime of (2 -  25 ) are
 [ 2   3   5   7   11   13   17   19   23 ]

 Prime of (2 -  101 ) are
 [ 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 ]

 Prime of (2 -  200 ) are
 [ 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 ]

Resultant Output Explanation

The output displays the prime numbers within the specified ranges. For example, for bitwise_sieve(25), the prime numbers from 2 to 25 are [2, 3, 5, 7, 11, 13, 17, 19, 23].

Time Complexity

The time complexity of the Bitwise Sieve algorithm is O(n log log n), where n is the upper limit of the range. This is because the algorithm eliminates the multiples of each prime number up to the square root of n. The space complexity is reduced to O(n/32), which represents the size of the sieve array in terms of bits.

Last updated on by Kalkicode




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