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

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

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

Конечное число

Рассчитать

Решето

2	3	4	5	6	7
8	9	10	11	12	13
14	15	16	17	18	19
20	21	22	23	24	25
26	27	28	29	30	31
32	33	34	35	36	37

 Ссылка  Сохранить  Виджет

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

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

Минимальное число

Максимальное число

Рассчитать

Найдено чисел

 

Число колонок

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

Время выполнения, мс

 

Время вывода, мс

 

 Ссылка  Сохранить  Виджет

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

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

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

//Граница поиска
n;
//заполнить массив с верхней границей n для поиска простых чисел единицами  
a ⟵ [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..до тех пор пока i²≤n
  • второй цикл: j=i²,i²+i,i²+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