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

Задачи и их решение / Решето Эратосфена

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа N, который приписывают древнегреческому математику Эратосфену Киренскому. Название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере обработки массива чисел нужные числа (простые) остаются, а ненужные (составные) исключаются.

Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA.

Для нахождения всех простых чисел не больше заданного числа N нужно выполнить следующие шаги:

  • Заполнить массив из N элементов целыми числами подряд от 2 до N.
  • Присвоить переменной p значение 2 (первого простого числа).
  • Удалить из массива числа от p2 до N с шагом p (это будут числа кратные p: p2, p2+p, p2+2p и т. д.).
  • Найти первое неудаленное число в массиве, большее p, и присвоить значению переменной p это число.
  • Повторять два предыдущих шага пока это возможно.

Все оставшиеся в массиве числа являются простыми числами от 2 до N

На рисунке проиллюстрирован алгоритм поиска простых чисел. Числа, отмеченные белым, являются удаленными.
Решето Эратосфена

Реализация

#include <iostream>
using namespace std;
int main() {
  int n;
  cout << "n= ";
  cin >> n;
  int *a = new int[n + 1];
  for (int i = 0; i < n+1; i++)
    a[i] = i;
  for (int p = 2; p < n+1; p++) {
    if (a[p] != 0) {
      cout << a[p] << endl;
      for (int j = p*p; j < n + 1; j += p)
        a[j] = 0;
    }
  }
cin.get(); cin.get();
}

Результат выполнения
Решето Эратосфена
Назад


Назад: Задачи и их решение

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *