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.

Etymology: 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

def sieve(n):
    primes = [True] * (n+1)
    primes[0] = primes[1] = False
    for i in range(2, int(sqrt(n))+1):
        for j in range(i**2, n+1, i):
            primes[j] = False
    return [i for i in range(len(primes)) if primes[i]]

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;
  nums.set();
  nums[0] = nums[1] = false;
  for(int i=2; i<=sqrt(n)+1; i++)
    for(int j=i*i; j<n+2; j+=i)	
      nums[j] = false;
 
  vector<int> primes;
  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).

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.

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