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

Решето Эратосфена

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

🐍 Python
n = int(input())
A = [1] * (n + 1)
C = []

for i in range(2, n + 1):
    if A[i] == 1:
        C.append(i)
        for j in range(i + i, n + 1, i):
            A[j] = 0

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

int main() {
    int n;
    cin >> n;
    
    vector<int> A(n + 1, 1);
    vector<int> C;
    
    for (int i = 2; i <= n; i++) {
        if (A[i] == 1) {
            C.push_back(i);
            for (int j = i + i; j <= n; j += i) {
                A[j] = 0;
            }
        }
    }
    
    for (int x : C) {
        cout << x << " ";
    }
    
    return 0;
}

Как работает решето Эратосфена?

Решето Эратосфена — это древний алгоритм для нахождения всех простых чисел до заданного числа n.

Алгоритм

  1. Создаём список чисел от 2 до n, считая все числа простыми
  2. Начинаем с 2 — оно простое, вычёркиваем все его кратные (4, 6, 8, ...)
  3. Переходим к следующему невычеркнутому числу (3) — оно простое, вычёркиваем его кратные
  4. Повторяем, пока не дойдём до √n

Пример для n = 30

Начинаем с 2: вычёркиваем 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30

Следующее простое — 3: вычёркиваем 6, 9, 12, 15, 18, 21, 24, 27, 30

Следующее простое — 5: вычёркиваем 10, 15, 20, 25, 30

Оставшиеся невычеркнутые числа — простые: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

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

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

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

Ввод: целое число n (n ≥ 2)

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

Пример:

30

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

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

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