Простые числа — это такие числа, которые делятся без остатка только на себя и единицу.
Вы конечно можете решить подобную задачу тривиальным способом (в цикле проверять все числа), но таким образом ваша программа в лидеры по производительности точно не выйдет.
Существует несколько алгоритмов более быстрого поиска простых чисел. Я решил рассмотреть программу которая использует так называемое «Решето Эратосфена».
Этот алгоритм строится на предположении, что можно сразу вычеркнуть из списка простых чисел все которые делятся на 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; }
Мой исходник.