Отсеиваем простые из миллиарда чисел быстрее, чем в Википедии

from timeit import timeit


def eratosthenes1(N):
    simp, nonsimp = [2], set()
    for i in range(3, N + 1, 2):
        if i not in nonsimp:
            nonsimp |= {j for j in range(3 * i, N + 1, 2 * i)}
            simp.append(i)
    return simp


def eratosthenes2(N):
    simp, nonsimp = [2, 3], {i for i in range(3, N + 1, 3)}
    for i in range(5, int(N ** 0.5), 2):
        if i not in nonsimp:
            nonsimp |= {j for j in range(i * i, N + 1, 2 * i)}
            simp.append(i)
    simp.extend([j for j in range(i, N + 1, 2) if j not in nonsimp])
    return simp


def eratosthenes3(N):  # Возвращает список простых чисел от 2 до N
    if N < 2:
        return []
    A = [False, True] * ((N + 2) // 2)
    A[2] = True
    for i in range(3, int(N ** 0.5 + 1.5), 2):
        if A[i]:
            for j in range(i * i, N + 1, 2 * i):
                A[j] = False
    return [i for i in range(2, N + 1) if A[i]]

# Самая быстрая версия, N = 10**8, ~13c
def eratosthenes4(N):  # Возвращает список простых чисел от 2 до N
    if N < 2: return []
    A = [False, True] * ((N + 2) // 2)  # Про чётные всё очевидно
    simps = [2]
    sqrtN = int(N ** 0.5 + 1.5)  # Корень плюс ещё немного
    sqrtN += 1 - sqrtN % 2  # Делаем нечётным (это пригодится позже)
    for i in range(3, sqrtN, 2):
        if A[i]:
            simps.append(i)
            for j in range(i * i, N + 1, 2 * i):
                A[j] = False
    simps.extend(i for i in range(sqrtN, N + 1, 2) if A[i])  # Вот здесь важно, что sqrtN нечётный
    return simps


def eratosthenes5(n):  # Решето Грайса и Мисра (David Gries, Jayadev Misra), асимптотика O(n)
    lsd = [0] * (n + 1)
    simp = []
    for i in range(2, n + 1):
        if lsd[i] == 0:
            simp.append(i)
            lsd[i] = i
        for p in simp:
            if p * i > n:
                break
            lsd[p * i] = p
    return simp


funcs = [obj for name, obj in globals().items() if name.startswith('erat')]
N = 10 ** 8
setup = 'from __main__ import funcs, N'
for i in range(len(funcs)):
    print(timeit(stmt='funcs[{}](N)'.format(i), setup=setup, number=1))
# 59.081
# 41.303
# 14.553
# 12.582 <- eratosthenes4 в 3+ раза быстрее
# 75.451

use std::time::Instant;

fn eratosthenes4(n: usize) -> Vec<usize> {
    if n < 2 {
        return Vec::new();
    }
    let mut tst = vec![true; (n + 1) / 2];
    let mut simps = vec![2];
    let mut sqrt_n = ((n as f64).sqrt() + 1.5) as usize;
    sqrt_n += 1 - sqrt_n % 2;
    for i in (3..sqrt_n).step_by(2) {
        if tst[i>>1] {
            simps.push(i);
            for j in (i * i..(n + 1)).step_by(2 * i) {
                tst[j>>1] = false;
            }
        }
    }
    for i in (sqrt_n..(n + 1)).step_by(2).filter(|x| tst[x>>1]) {
        simps.push(i);
    }
    return simps;
}


fn main() {
    let now = Instant::now();
    let n = 1_000_000_000;
    let res = eratosthenes4(n);
    let dur = Instant::now().duration_since(now);
    println!("Duration: {:?}, len: {}", dur, res.len());
    // Duration: 6.0877631s, len: 50847534
}