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

Он делает это, итеративно помечая как составные числа, кратные каждому простому числу, начиная с первого простого числа, 2. Кратные числа данного простого числа генерируются как последовательность чисел, начиная с этого простого числа, с постоянной разницей между ними, равной тот премьер.

Вместо того, чтобы проверять каждое число как простое (подход грубой силы), мы будем работать с группами. Во-первых, мы создадим вектор логических значений, где все значения true. Остальная работа будет только над этим вектором.

Длина вектора равна пределу, до которого мы находим все простые числа, скажем, N. Теперь в этом векторе присвойте всем четным индексам, начиная с 3, значение false, поскольку все четные числа, кроме 2, не являются простыми.

Теперь для всех нечетных чисел пометьте их кратные как false, так как они также не являются простыми.

Теперь пометьте 0-й и 1-й индексы как false.

Все остальные индексы, для которых задано значение true, являются простыми числами до N.

#include <bits/stdc++.h>
using namespace std;
void sieveOfEratosthenes(int n){
 // Create a boolean array of length n+1 for all numbers from 0 to n
 bool isPrime[n + 1];
 // Set all the elements to true in the isPrime array
 memset(isPrime, true, sizeof(isPrime));
for (int p = 2; p * p <= n; p++){
  // If isPrime[p] is true, then it is a prime
  if (isPrime[p] == true)
  {
   // Update all multiples
   // of p greater than or
   // equal to the square of it
   // numbers which are multiple
   // of p and are less than p^2
   // are already been marked.
   for (int i = p * p; i <= n; i += p)
    isPrime[i] = false;
  }
 }
 for (int p = 2; p <= n; p++)
  if (isPrime[p])
   cout << p << " ";
}
// Driver Code
int main(){
 int n = 30;
 cout << "Prime numbers smaller "
  << " than or equal to " << n << endl;
 sieveOfEratosthenes(n);
 return 0;
}

Временная сложность классического алгоритма решета Эратосфена составляет **O(N log (log N))**. Многие варианты этого алгоритма также могут быть найдены с еще большей временной сложностью.

Подробнее читайте в такой статье на https://codeunlock.in/

Оригинал статьи читать здесь