Ненормальное программирование (серия 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 секунд, что несколько медленнее, чем «решето Эратосфена».

Эпилог

Вывод будет простым: не пользуйтесь перебором, а сейте через решето. А вот выбор решета остается за вами… ;)