Практическая работа «Решето Эратосфена»
Решето Эратосфена
Очень часто в прикладных задачах, например, при шифровании с помощью алгоритма RSA (напомним, что мы планируем написать программу шифрования с использованием данного алгоритма), широко используются простые числа. Основные задачи при работе с простыми числами – это проверка числа на простоту и нахождение всех простых чисел в заданном диапазоне. Большой диапазон требует эффективных алгоритмов.
Пусть задано некоторое натуральное число N и требуется найти все простые числа в диапазоне от 2 до N. Самое простое (но неэффективное) решение этой задачи состоит в том, что в цикле перебираются все числа от 2 до N, и каждое из них отдельно проверяется на простоту. Например, можно проверить, есть ли у числа k делители в диапазоне от 2 до Ök. Если ни одного такого делителя нет, то число k простое.
Данный метод при больших значениях N работает очень медленно и имеет асимптотическую сложность O(NÖN).
Греческий математик Эратосфен Киренский (276-194 гг. до н.э.) предложил другой алгоритм, который работает намного быстрее, его сложность оценивается как O(N log log N):
1) выписать все числа от 2 до N;
2) начать с k = 2;
3) вычеркнуть все числа, кратные k (2k, 3k, 4k и т.д.);
4) найти следующее не вычеркнутое число и присвоить его переменной k;
5) повторять шаги 3 и 4, пока k < N.
Название «решето» метод получил потому, что, согласно легенде, Эратосфен писал числа на дощечке, покрытой воском, и прокалывал дырочки в тех местах, где были написаны составные числа. Поэтому дощечка являлась неким подобием решета, через которое «просеивались» все составные числа, а оставались только числа простые. Эратосфен дал таблицу простых чисел до 1000.
|
|
|
Покажем работу алгоритма при N = 12:
2 3 4 5 6 7 8 9 10 11 12
Первое не вычеркнутое число – 2, поэтому вычеркиваем все чётные числа больше 2:
2 3 4 5 6 7 8 9 10 11 12
Далее вычеркиваем все числа, кратные 3:
2 3 4 5 6 7 8 9 10 11 12
А все числа, кратные 5 и 7 уже вычеркнуты. Таким образом, получены простые числа 2, 3, 5, 7 и 11.
Главной проблемой реализации решета Эратосфена на вычислительных машинах является не количество выполняемых операций, а требования по объёму занимаемой памяти. При больших значениях N , диапазон простых чисел может превысить доступную память.
Классический алгоритм можно улучшить, уменьшив количество операций. Заметьте, что при вычеркивании чисел, кратных трём, нам не пришлось вычеркивать число 6, так как оно уже было вычеркнуто. Кроме того, все числа, кратные 5 и 7, к последнему шагу тоже оказались вычеркнуты.
Предположим, что мы хотим вычеркнуть все числа, кратные некоторому k, например, k = 5. При этом числа 2k, 3k, и 4k уже были вычеркнуты на предыдущих шагах, поэтому нужно начать не с 2k, а с k2. Тогда получается, что при k2 > N вычёркивать уже будет нечего, что мы и увидели в примере.
|
|
|
Поэтому можно использовать улучшенный алгоритм:
1) выписать все числа от 2 до N;
2) начать с k = 2;
3) вычеркнуть все числа, кратные k, начиная с k2;
4) найти следующее не вычеркнутое число и присвоить его переменной k;
5) повторять шаги 3 и 4, пока k2<=N.
Чтобы составить программу, нужно определить, что значит «выписать все числа» и «вычеркнуть число». Один из возможных вариантов хранения данных – массив логических величин с индексами от 2 до N.
Пусть N = 100. Тогда массив, показывающий выколото какое-то число или нет, в программе можно объявить так:
На PascalABC.NET:
const N = 100;
Var
I, k : integer;
A : array[2..N] of boolean;
На С++:
const int N = 100;
bool A [ N +1];
Если число i не вычеркнуто, будем хранить в элементе массива A[i] истинное значение (true), если вычеркнуто – ложное (false).
В С++ нумерация элементов массива начинается с нуля. Для удобства использовать «естественную» нумерацию (с единицы) можно выделить на один элемент больше. При этом нулевой элемент массива использоваться не будет.
|
|
|
В самом начале нужно заполнить массив истинными значениями (все числа не вычеркнуты):
На PascalABC.NET:
for i:= 2 to N do
A[i]:= True;
На С++:
for (int i = 2; i <= N; i++)
A [ i ] = true ;
В основном цикле выполняется описанный выше алгоритм:
На PascalABC.NET:
k:= 2;
while k*k <= N do begin
if A[k] then begin
i:= k*k;
while i <= N do begin
A[i]:= False;
i:= i + k
End;
End;
k:= k + 1
end;
На С++:
int k = 2;
while (k*k <= N)
{
if (A[k])
{
int i = k*k;
while (i <= N)
{
A[i] = false;
i += k ;
}
}
k ++;
}
Обратите внимание, что для того чтобы вообще не применять вещественную арифметику, мы заменили условие k<= Ö N на равносильное условие k2<=N, в котором используются только целые числа. N
После завершения этого цикла не вычеркнутыми остались только простые числа, для них соответствующий элемент массива содержит истинное значение. Эти числа нужно вывести на экран:
На PasdcalABC.NET:
for i:= 2 to N do
if A[i] then
writeln(i);
На С++:
for (int i = 2; i <= N; i++)
if ( A [ i ])
cout << i << " ";
Практическая работа «Решето Эратосфена»
|
|
|
1. Напишите программу, которая выводит все простые числа от 1 до N, используя решето Эратосфена.
2. Напишите программу, которая подсчитывает количество простых чисел от 1 до N, используя решето Эратосфена.
3. Напишите программу, которая проверяет простое ли число, используя решето Эратосфена.
4. Заполните таблицу
| N | Количество простых чисел от 1 до N | Примерное время работы программы, секунд |
| 200 | ||
| 2 000 | ||
| 2 000 000 | ||
| 200 000 000 | ||
| 20 000 000 000 |
Выводы к таблице:
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
__________________________________________________________________
Дата добавления: 2019-11-16; просмотров: 839; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!