Prime sieves are common devices for generating prime numbers in a given range. These lists can be used for quick verification of relatively small prime numbers (typically ranging up to 10⁶ or greater), in particular when many such verifications may be necessary.

A sieve¹⁾ is a physical metaphor (i.e., a mesh bowl in a kitchen) for an algorithmic technique used in number theory to “sift out” a class of numbers in a given set or range.

sieve.py

from math import *
 
def sieve(n):
    primes = [True] * (n+1)                             # generate a list of primes
    primes[0] = primes[1] = False
    for i in range(2, int(sqrt(n))+1):                  # filter out non-primes
        for j in range(i**2, n+1, i):
            primes[j] = False
    return [i for i in range(len(primes)) if primes[i]] # generate primes from True values
 
primes = sieve(1000000)

sieve.cpp

#include <bitset>
#include <cmath>
#include <iostream>
#include <vector>
 
using namespace std;
 
const int MAX_PRIMES=10000000;
 
vector<int>sieve(int n) {
  bitset<MAX_PRIMES+1> nums;      // generate a list of primes
  nums.set();                     // set all values to true
  nums[0] = nums[1] = false;
  for(int i=2; i<=sqrt(n)+1; i++) // filter out non-primes
    for(int j=i*i; j<n+2; j+=i)	
      nums[j] = false;
 
  vector<int> primes;              // generate primes from true values
  for(int i=0; i<nums.size(); i++)
    if(nums[i] == true)	
      primes.push_back(i);
 
  return primes;
}  
 
int main() {
  vector<int> primes = sieve(MAX_PRIMES);
 
  return 0;
}

Operation Sieve of Eratosthenes is quite simple. The sieve starts by assuming all numbers in a given range (2..n) are prime (True values in our list). Then for each number, i, from (2..sqrt(n)) we eliminate any multiples of i by setting them to False.²⁾ After completion, the True values indicate indices that are prime (the list of which is generated by the final list comprehension in the return statement).

A C++ bitset³⁾ is used for additional time/space efficiency to store true/false values. A vector would also work, but at an increased cost of time and space.

The Sieve of Eratosthenes is not the fastest prime sieve available, but it is quick to code, easy to understand and modify, and sufficiently fast for some practical applications.

Time Complexity: O((n log n)(log log n))⁴⁾
Space Complexity: O(n)

This implementation (Python3) should work reliably for primes up to 10⁶ in competition settings.

Redo benchmarks on desktop.

Implementations are from the pseudocode provided in the Wikipedia article on the Sieve of Eratosthenes⁵⁾.