Определение

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

Алгоритм достаточно тривиален: будем перебирать числа по возрастанию, начиная с , зачёркивая все числа, кратные текущему. Например, при обработке числа будут зачёркнуты числа . Если мы обнаружили незачёркнутое число, это значит, что оно простое.

Визуализация работы решета Эратосфена:

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

Работу решета можно значительно ускорить, если начинать зачёркивать числа, кратные , не с , а с . Ведь числа уже были зачёркнуты при обработке чисел

Реализация

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>

using namespace std;

bool sieve[1000001];    //решето
vector<int> primes;     //вектор, в который будут добавляться простые числа

void compute_primes(int n) {
    for (int i = 2; i <= n; i++) {   //Изначально все числа не вычеркнуты.
        sieve[i] = true;
    }

    for (int i = 2; i <= n; i++) {
        if (sieve[i]) {     //если i не вычеркнуто
            primes.push_back(i);

            for (int j = i * i; j <= n; j += i) {    //вычеркиваем все кратные числа начиная с i^2
                sieve[j] = false;
            }
        }
    }
}

int main() {
    compute_primes(1000000);

    cout << "Prime numbers: ";
    for (int i: primes) {
        cout << i << ", ";
    }
}