Ненормальное программирование (серия 3). Не такое уж и простое это простое число

Достаточно часто при решении задач приходится сталкиваться с нахождением простых чисел. Сегодня мы рассмотрим несколько способов, которыми можно решить данную проблему. Если заинтересовало — пожалуйте под кат.
Для начала, вспомним, что же такое простое число.
Простое число — это натуральное число, имеющее ровно два различных натуральных делителя: единицу и само себя.
Казалось бы, нет ничего сложного в том, чтобы посчитать, сколько у числа делителей, и решить, простое оно или нет. Да, в этом нет ничего сложного, и отсюда вытекает самый простой способ определения простых чисел.
1. Перебор делителей
С этим способом знакомы, наверное, все, кто хоть как-то связан с программированием. Алгоритм здесь достаточно прост — перебрать все делители у числа и, если их всего 2 (единица и само число), то число простое:for x := 1 to n do
begin
k := 0;
for i := 2 to x div 2 do
if x mod i = 0 then
inc(k);
if k = 0 then
is_prime[x] := true;
end;
Примечание: Чтобы оценить быстродействие алгоритмов с минимальными погрешностями, мы будем сначала заполнять массив типа Boolean значениями в соответствии с тем, является число простым или нет, и измерять только время заполнения массива, т.к. вывод чисел на экран серьезно замедляет производительность.
Пишем код, запускаем при n = 100 000 и… ждем-с. Работа алгоритма занимает около 10 секунд. Хм, учитывая, что в задачах n бывает даже больше, а время работы программы ограничено 1-2 секундами, нужно поискать более быстрые алгоритмы.
2. Решето Эратосфена
Алгоритм поиска простых чисел, который носит название «Решето Эратосфена», часто изучают в средней школе. Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:- Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
- Пусть переменная p изначально равна двум — первому простому числу.
- Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …)
- Найти первое не зачеркнутое число, большее, чем p, и присвоить значению переменной p это число.
- Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
На Pascal’е этот алгоритм можно записать следующим образом:
for i := 2 to trunc(sqrt(n)) do
if is_prime[i] then
j := i * i;
while j <= n do
begin
if is_prime[j] then
is_prime[j] := false;
inc(j, i);
end;
При n = 100 000 000 алгоритм отработал за 3 секунды. Первый алгоритм при таких входных данных я просто боюсь запускать. Видно, что повышение производительности просто огромно. К тому же алгоритм «решета Эратосфена» не так уж и сложен для запоминания.
3. Решето Аткина
Напоследок покажу еще один, чуть более сложный алгоритм — решето Аткина — это быстрый современный алгоритм нахождения всех простых чисел до заданного целого числа N. Основная идея алгоритма состоит в использовании неприводимых квадратичных форм (представление чисел в виде a*x^²+b*y^²). Отдельный этап алгоритма вычеркивает числа, кратные квадратам простых чисел. Алгоритм был создан А.О.Л. Аткиным и Д.Ю. Бернштайном, отсюда и его название.Алгоритм описывать не буду, покажу лишь код:
for x := 1 to trunc(sqrt(n)) do
for y := 1 to trunc(sqrt(n)) do
begin
p := 4 * sqr(x) + sqr(y);
if (p <= n) and ((p mod 12 = 1) or (p mod 12 = 5)) then
is_prime[p] := not is_prime[p];
p := 3 * sqr(x) + sqr(y);
if (p <= n) and (p mod 12 = 7) then
is_prime[p] := not is_prime[p];
p := 3 * sqr(x) - sqr(y);
if (x > y) and (p <= n) and (p mod 12 = 11) then
is_prime[p] := not is_prime[p];
end;
for i := 5 to n do
if is_prime[i] then
begin
k := sqr(i);
p := k;
while p <= n do
begin
is_prime[p] := false;
p := p + k;
end;
end;
При тех же n = 100 000 000 алгоритм работает около 6 секунд, что несколько медленнее, чем «решето Эратосфена».
Эпилог
Вывод будет простым: не пользуйтесь перебором, а сейте через решето. А вот выбор решета остается за вами… ;)-
chermenin,
- 28 мая 2012, 15:05
- рейтинг: +4
- belan
- 28 мая 2012, 15:19
— замечательный анализ, для меня важно, что не надо тратить время на поиски — всё проанализировано и объяснено!
Похожие записи для топика «Ненормальное программирование (серия 3). Не такое уж и простое это простое число»