Статья Автор: Лебедев Дмитрий Алексеевич

Решето, как способ решения задач по поиску лучшего

Наиболее известным способом нахождения/перебора простых чисел является "Решето Эратосфена".
Описание этого метода можно найти в интернете, здесь попробуем привести программу,
получающую множество всех простых чисел, не превосходящих заданного числа.
Постановка задачи:
Найти множество всех простых чисел, которые не больше заданного N
Решения вынесены в подпрограммы и частично "оптимизированы"

def sieve_eratosfen (N):
    A = [False, False, True] + [True, False]*(N//2)
    kk = 2
    while kk * kk < N : kk += 1
    k = 3
    while k <  kk :
        if A[k]:
            for i in range (k*k, N+1, k): 
                A[i] = False
        k += 2
    return [2] + [i for i in range(3, N+1, 2) if A[i]]
N = int(input())
S = sieve_eratosfen (N)
print(f'Найдено {len(S)} простых чисел\n {S}')

#include <iostream>
#include <vector>

using namespace std;
auto sieve_eratosfen (int N){
  vector <bool> M(N, true);
  int kk = 2;
  while (kk * kk < N ) {kk+=1;}
  for (int i = 2; i <= N; i += 2) {M[i] = false;}
  int k = 3;
  while (k < kk ){
    if (M[k]) {
      for (int i = k * k; i <= N; i += k){M[i] = false;}
    }
    k += 2;
  }
  vector<int> P;
  P.push_back(2);
  for (int i = 3;  i <=N; i += 2){
    if (M[i]) {P.push_back(i);}
  }
  return P;
}

int main()
{
  clock_t start = clock();
  int N;
  cin >> N;
  auto Pr = sieve_eratosfen (N);
  printf("%d\n",Pr.size()) ;
  for (auto p : Pr) {printf("%d ", p);} 
  return 0;
}

Метод решета можно применять не только для отбора простых чисел, но и для подсчета

количества делителей
суммы делителей
и т.п. (функция Эйлера, ...)

Покажем, как находить число делителей.
Создадим "индексный массив" из единиц (на 1 делиться все) и для числа i будем добавлять +1 во все ячейки, кратные i

def sieve_n_divisors (N):
    A = [0] + [1]* N
    for k in range (2, N + 1):
      for kk in range (k, N + 1, k):
        A[kk] += 1
    return A
N = int(input())
KD = sieve_n_divisors (N)
print(*[f'KD[{i}]={KD[i]} ' for i in range(1,N+1)])

Печать