Нахождение простых чисел: полный разбор с программным кодом

Решето Эратосфена с битовыми операциями (экономия памяти)

Вместо списка булевых значений используется целое число или массив байтов. Каждый бит соответствует одному числу.

def sieve_bitarray(n):
    if n < 2:
        return []
    # Используем bytearray для хранения флагов (1 байт на число)
    is_prime = bytearray(b'\x01') * (n + 1)
    is_prime[0] = is_prime[1] = 0
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            step = i
            start = i * i
            is_prime[start:n+1:step] = b'\x00' * ((n - start)//step + 1)
    return [i for i, flag in enumerate(is_prime) if flag]

print(sieve_bitarray(40))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Пояснение: bytearray занимает 1 байт на элемент вместо 28 байт (для bool в Python). Операция присваивания среза b'\x00' * количество устанавливает все кратные в ноль за один вызов.

Решето Эратосфена с оптимизацией чётных чисел

Можно хранить информацию только для нечётных чисел, сократив память вдвое.

def sieve_odd_only(n):
    if n < 2:
        return []
    if n == 2:
        return [2]
    # is_prime[i] соответствует числу 2*i+3
    size = (n - 1) // 2
    is_prime = [True] * size
    for i in range(int(n ** 0.5) // 2):
        if is_prime[i]:
            # число = 2*i+3
            p = 2 * i + 3
            # начинаем с p*p = (2*i+3)^2 = 4*(i^2) + 12*i + 9 = 2*(2*i^2+6*i+4)+1
            step = p
            start = (p * p - 3) // 2  # индекс для p^2
            is_prime[start::step] = [False] * ((size - start + step - 1) // step)
    result = [2] + [2*i+3 for i, val in enumerate(is_prime) if val]
    return result

print(sieve_odd_only(50))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Здесь сложнее индексация, но выигрыш в памяти и скорости за счёт меньшего количества операций.

Параллельное вычисление простых чисел (multiprocessing)

Для больших N (например, до 10^7) можно разделить диапазон на части и обработать параллельно.

import multiprocessing as mp

def sieve_segment(start, size):
    # Решето на отрезке [start, start+size)
    limit = int((start + size) ** 0.5) + 1
    # сначала найдём все простые до limit
    is_prime_base = [True] * (limit + 1)
    is_prime_base[0] = is_prime_base[1] = False
    for i in range(2, int(limit ** 0.5) + 1):
        if is_prime_base[i]:
            for j in range(i*i, limit+1, i):
                is_prime_base[j] = False
    bases = [i for i, v in enumerate(is_prime_base) if v]
    
    # Теперь работаем с сегментом
    segment = [True] * size
    first = start
    for p in bases:
        start_val = max(p*p, (first + p - 1)//p * p)
        for j in range(start_val, first+size, p):
            segment[j - first] = False
    return [first + i for i, v in enumerate(segment) if v]

def parallel_primes(n, num_workers=4):
    if n < 2:
        return []
    chunk_size = (n - 1) // num_workers + 1
    ranges = []
    for i in range(num_workers):
        start = 2 + i * chunk_size
        end = min(start + chunk_size, n + 1)
        if start < end:
            ranges.append((start, end - start))
    with mp.Pool(num_workers) as pool:
        results = pool.starmap(sieve_segment, ranges)
    # объединение результатов (могут быть дубли? нет)
    primes = []
    for r in results:
        primes.extend(r)
    return sorted(primes)

# для демонстрации возьмём небольшое n
print(parallel_primes(50, 2))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Внимание: при малых N параллелизм не даёт выигрыша из-за накладных расходов. Для N=10^7 может ускорить в 2-3 раза на многоядерном процессоре.

Использование библиотеки numpy для векторизованного решета

Numpy позволяет выполнять операции над массивами быстрее, чем чистые циклы Python.

import numpy as np

def sieve_numpy(n):
    if n < 2:
        return []
    is_prime = np.ones(n+1, dtype=bool)
    is_prime[0:2] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            is_prime[i*i:n+1:i] = False
    return np.where(is_prime)[0].tolist()

print(sieve_numpy(50))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Скорость может быть выше решета на чистых списках для больших N за счёт низкоуровневой реализации. Однако импорт numpy оправдан только если библиотека уже используется в проекте.

Решето Эратосфена с Wheel factorization (оптимизация путём пропуска чисел, кратных 2,3,5)

Сначала предварительно отсеиваются числа с малыми простыми делителями, затем решето применяется к остаткам. Пример для wheel 2*3=6.

import math

def wheel_sieve(n):
    if n < 2:
        return []
    # малые простые
    small_primes = [2, 3, 5]
    limit = int(math.isqrt(n))
    # отсеиваем маленькие
    marks = [False] * (n+1)
    for p in small_primes:
        for multiple in range(p, n+1, p):
            marks[multiple] = True
    # теперь решето среди чисел вида 6k±1 (кроме кратных 2,3)
    for i in range(7, limit+1, 2):
        if not marks[i]:
            step = i if i%6==1 else i*2  # упрощение
            # на самом деле нужно вычёркивать кратные
            start = i*i
            if start > n:
                break
            for j in range(start, n+1, i):
                marks[j] = True
    # собираем непомеченные
    return [i for i in range(2, n+1) if not marks[i]]

print(wheel_sieve(100))

[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]

Реализация выше не совершенна, но демонстрирует идею. Полное Wheel factorization (2*3*5 = 30) даёт дополнительное ускорение.