homechevron_rightУчебаchevron_rightМатематика

Поиск простых чисел. Решето Эратосфена.

Калькулятор находит простые числа используя алгоритм, известный как "Решето Эратосфена"

Данный калькулятор находит простые числа методом, известным с античных времен, как решето Эратосфена. Напомним, простые числа, не имеют других делителей, кроме себя и единицы.
В результате работы калькулятора отобразится матрица содержащая составные числа (серые) и простые числа (черные).

PLANETCALC, Решето Эратосфена

Решето Эратосфена

Решето
 



Это был демонстрационный калькулятор с самым примитивным алгоритмом. Диапазон чисел в нем ограничен до 1000 ввиду избыточного вывода и ресурсоемкой реализации. Калькулятор и его исходный код будет полезен, тем кто хочет понять логику древнегреческого ученого, придумавшего метод в 3 веке до нашей эры.
Следующий калькулятор является развитием идеи Эратосфена, без избыточных операций и с оптимизацией по объему используемой памяти. Тут уже (если позволит ваш компьютер) можно попробовать посчитать простые числа до нескольких миллиардов. Однако будьте осторожны - с большой конечной границей память и процессор вашего устройства будут нещадно использоваться.

PLANETCALC, Решето Эратосфена, оптимизированное

Решето Эратосфена, оптимизированное

Найдено чисел
 
Время выполнения, мс
 
Время вывода, мс
 

Все найденные простые числа можно выгрузить в csv файл, однако тут еще раз предупреждаю - все происходит в памяти вашего компьютера и при выгрузке будет отхвачен пятикратный её объем. Мой старенький ноутбук с 4Гб оперативной памяти довольно легко справился с просеиванием 26+ миллионов простых чисел из диапазона в полмиллиарда, а вот выгрузить его в csv уже не сумел.

Алгоритм Решето Эратосфена

Описание алгоритма в псевдокоде:

//Граница поиска
n;
//заполнить массив с верхней границей n для поиска простых чисел единицами  
a ⟵ [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1...];
//первый цикл
для i=2,3,4..≤n:
    если  a[i] = 1:
         //второй цикл
         для j = 2i,3i,4i .. ≤n:
              a[i]⟵0
output ⟵ все i в диапазоне 2 ≤ i ≤ n, для которых a[i]=1

Оптимизации алгоритма

  • как нетрудно заметить оригинальный алгоритм проходится несколько раз по одним и тем же элементам массива, чтобы этого избежать мы меняем
    • первый цикл для i=2,3,4..до тех пор пока i2≤n
    • второй цикл: j=i2,i2+i,i2+2i... ≤n
  • вместо логических данных, занимающих 1 байт можно использовать 1 бит - и тем самым сократить объем занимаемой памяти в 8 раз
  • как нетрудно заметить все чётные числа кроме 2 не являются простыми, приняв во внимание этот факт мы делаем следующее:
    • сокращаем объем занимаемой памяти еще в два раза
    • изменяем алгоритм таким образом:
      //первый цикл
      для i=3,5,7..до тех пор пока  i²≤n
      если  a[(i-1)/2] = 1:
       //второй цикл
       для j = i²,i²+2i,i²+4i .. ≤n:
            a[(i-1)/2]⟵0
      output ⟵ 2, все нечетные i в диапазоне 3 ≤ i ≤ n, для которых a[(i-1)/2]=1
Ссылка скопирована в буфер обмена
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Поиск простых чисел. Решето Эратосфена.

Комментарии