← Назад к математике

Линейное решето Эратосфена

Нахождение всех простых чисел до n за линейное время O(n)

🐍 Python
n = int(input())
D = [i for i in range(n + 2)]
P = []

for i in range(2, n):
    if D[i] == i:
        P.append(i)
    for j in P:
        if i * j > n or D[i] < j:
            break
        D[i * j] = j

print(*P)
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> D(n + 2);
    for (int i = 0; i <= n + 1; i++) {
        D[i] = i;
    }
    
    vector<int> primes;
    for (int i = 2; i < n; i++) {
        if (D[i] == i) {
            primes.push_back(i);
        }
        for (int j : primes) {
            if (i * j > n || D[i] < j) break;
            D[i * j] = j;
        }
    }
    
    for (int p : primes) {
        cout << p << " ";
    }
    
    return 0;
}

Линейное решето Эратосфена

Обычное решето Эратосфена имеет сложность O(n log log n). Линейное решето работает за O(n), так как каждое составное число вычёркивается ровно один раз.

Идея алгоритма

Преимущества

Временная сложность: O(n)

Пространственная сложность: O(n)

Формат ввода и вывода

Ввод: n — верхняя граница

Вывод: все простые числа до n

Пример:

30

Вывод: 2 3 5 7 11 13 17 19 23 29

Попробовать онлайн

Результат появится здесь...