Находим простые числа на заданном отрезке при помощи решета Эратосфена и языка С++

Простые числа — это такие числа, которые делятся без остатка только на себя и единицу.
Вы конечно можете решить подобную задачу тривиальным способом (в цикле проверять все числа), но таким образом ваша программа в лидеры по производительности точно не выйдет.
Существует несколько алгоритмов более быстрого поиска простых чисел. Я решил рассмотреть программу которая использует так называемое «Решето Эратосфена».
Этот алгоритм строится на предположении, что можно сразу вычеркнуть из списка простых чисел все которые делятся на 2, а затем найти первое не вычеркнутое число и удалить из списка все ему кратные. Так необходимо продолжать до тех пор, пока не будет достигнут предел изучаемой области.
Чтобы понять просто взгляните на картинку:

…думаю вы простите меня за то, что я «спёр» её у википедии..

Итак приступим к созданию программы.
Нам понадобится только библиотека iostream:

#include <iostream>
using namespace std;

В главной функции программы создадим константу — предел области изучения.

const int N = 100;

И рабочий массив

bool n[N];

Прежде всего заполним массив значениями true (предполагаем что числа простые).

for (int i=2;i<=N;i++) {
     n[i] = true;
}

Начинаем с двойки, т.к. заведомо знаем, что это число простое.
Теперь начинаем проходить массив «простых» чисел, попутно устанавливая по изложенному выше алгоритму, необходимые значения в false.

for (int i=2;i<=N;i++) {
     if (n[i] == true) {
         for (int j=i*i;j<=N;j+=i)
             n[j] = false;
    }
}

После этой операции мы получим массив в котором i-ый элемент со значением true — простое число.
Осталось вывести результат на экран:

for (int i=2;i<=N;i++) {
  if (n[i] == true)
      cout << i << endl;
}

Мой исходник.

 

Похожий код:

Фото аватара
Алексей Петров

Программист, разработчик с 5 летним опытом работы. Учусь на разработчика игр на Unity и разработчика VR&AR реальности (виртуальной реальности). Основные языки программирования: C#, C++.

Оцените автора
Бла, бла код
Добавить комментарий