Решето Эратосфена — это алгоритм нахождения всех простых чисел до некоторого целого числа
n, который приписывают древнегреческому математику Эратосфену Киренскому. Такое название алгоритм получил потому, что во времена Эратосфена, для нахождения простых чисел, использовались дощечки покрытой воском в которых прокалывались дырочки (зачеркивались или “обнулялись” составные числа).Суть этого алгоритма заключается в следующем. Составим список чисел, которые нам нужно “просеять” начиная с двойки.
i = 2. Зачеркнем в этом списке все числа с шагом i + 2, т. е. 4, 6, 8, 10, 12... (это числа кратные 2).
Далее переходим к первому, после двойки, незачеркнотому числу – это
3. i = 3. Зачеркиваем все незачеркнутые числа с шагом i + 3: 9, 15, 21, 27... (числа кратные трем)
Следующее число
i = 5. Зачеркиваем числа с шагом i + 5, при этом, обращаем внимание, что зачеркивание можно начать с 25 (i2):
Последним числом в данном списке является
i = 7:
На этом этапе мы получили все целые числа от
2 до 101, включительно. Выписываем все незачеркнутые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101В компьютерной программе идею алгоритма “Решета Эратосфена” можно реализовать следующим образом.
- Создадим массив чисел от
2доn. - Пусть переменная
iизначально равна2— первому простому числу. Организуем структуру вложенных циклов. Во внешнем цикле со счетчикомiпроходим по всем элементам массива. - Находим первое ненулевое число в массиве. Это будет следующее целое число. Присваиваем значение
2 * iвспомогательной перемененнойp. Во вложенном цикле будем обнулять (“просеивать”) в массиве элементы с индексомpот2 * iдоn, увеличивая значение перемененнойpнаiс каждым шагом вложенного цикла (это будут числа кратные текущему простому числуi: 2 * i, 3 * i, 4 * i, ...). - Повторяем шаги 3 и 4, пока это возможно.
В итоге, массив будет содержать только нули и целые числа от 2 до n. Буквальное воспроизведение данного алгоритма представлено в программе 1.
Программа 1
#include <iostream>
#include <vector>
using namespace std;
int main() {
long long n(100);
vector<long long> prime;
for (long long i = 0; i < n + 1; i++)
prime.push_back(i);
prime[0] = prime[1] = 0;
auto i = 2ll;
while (i <= n) {
if (prime[i]) {
long long p = i + i;
while (p <= n) {
prime[p] = 0;
p = p + i;
}
}
i++;
}
for (long long i = 0; i < n + 1; i++)
if (prime[i])
cout << prime[i] << " ";
return 0;
}
Этот алгоритм можно существенно улучшить.
- Вместо значений элементов массива можно использовать его индексы, что значительно уменьшит размер используемой памяти. Тогда, в качестве типа элементов массива, можно выбрать тип
bool. - При заполнении массива единицами с нулевого элемента, начинать шаги внешнего цикла можно с
2(равно как и вывод готового массива). - На шаге №3 числа можно обнулять начиная с числа p2, потому что все меньшие числа, кратные
p, обязательно имеют простой делитель меньшеp(эти элементы ранее уже были обнулены). Останавливать алгоритм можно, когда p2 станет больше, чемn.
Программа будет выглядеть компактнее, если вместо цикла while использовать цикл for. В программе 2 представлен измененный алгоритм с комментариями.
Программа 2
#include <iostream>
#include <vector>
using namespace std;
int main() {
auto n = 100ll;
// Заполняем массив единицами
vector<bool> prime (n + 1, true);
// Исключаем числа 0 и 1
prime[0] = prime[1] = false;
for (long long i = 2; i * i <= n; ++i)
if (prime[i]) // Если элемент не нулевой
// то, начиная с квадрата этого элемента,
for (long long j = i * i; j <= n; j += i)
// с шагом i, обнуляем (просеиваем) элементы
prime[j] = false;
// выводим те индексы элементов,
for (size_t i = 2; i < prime.size(); i++)
// которые не равны нулю
if (prime[i])
cout << i << " ";
return 0;
}
Такая реализации алгоритма имеет временную сложность O(n log log n).
В виде блок-схемы алгоритм можно изобразить следующим образом:
[Скачать в формате PDF]
Реализуем алгоритм “Решето Эратосфена” в виде функции.
Программа 3
#include <iostream>
#include <vector>
using namespace std;
void sieve(long long n);
vector<bool> prime;
int main() {
long long k;
cout << "Граница поиска целых чисел = ";
cin >> k;
sieve(k);
for (size_t i = 2; i < prime.size(); i++)
if (prime[i])
cout << i << " ";
return 0;
}
void sieve(long long n) {
for (long long i = 0; i <= n; i++)
prime.push_back(true);
prime[0] = prime[1] = false;
for (long long i = 2; i * i <= n; ++i)
if (prime[i])
for (long long j = i * i; j <= n; j += i)
prime[j] = false;
}
Если вам нужно создать функцию, которая должна часто обращаться к массиву с проверкой: является ли число-аргумент простым, то лучшим решением будет поместить массив в структуру данных set. Эта структура данных позволяет производить поиск очень эффективно. Например.
Программа 4
#include <iostream>
#include <vector>
#include <set>
using namespace std;
void sieve(long long n);
bool ssieve(long long n);
vector<bool> prime;
set<long long> eratosphen;
int main() {
long long k, test;
cout << "Граница поиска целых чисел = ";
cin >> k;
sieve(k);
cout << "Число для проверки = "; cin >> test;
if (ssieve(test))
cout << "Это число является простым" << endl;
else
cout << "Это число не является простым" << endl;
return 0;
}
void sieve(long long n) {
for (long long i = 0; i <= n; i++)
prime.push_back(true);
prime[0] = prime[1] = false;
for (long long i = 2; i * i <= n; ++i)
if (prime[i])
for (long long j = i * i; j <= n; j += i)
prime[j] = false;
for (long long i = 0; i <= n; i++)
if (prime[i])
eratosphen.emplace(i);
}
bool ssieve(long long n) {
return eratosphen.find(n) != eratosphen.end();
}
Продумайте свой алгоритм так, чтобы массив целых чисел в программе был получен только один раз, а остальные подзадачи решались на уже полученных данных.
(1 оценок, среднее: 5,00 из 5)
Загрузка...
