Таблица простых чисел – онлайн калькулятор

Онлайн калькулятор для получения списка или таблицы простых чисел в заданном промежутке – от миллионов до миллиардов и намного больше. Имеется возможность поиска простых чисел, имеющих более 16-ти разрядов в десятичной системе исчисления, используя длинную арифметику.

Онлайн калькулятор

Найти простые числа в промежутке:

Описание калькулятора

Выбор промежутка

После ввода натуральных чисел , будет осуществляться поиск простых чисел на отрезке .
При выборе промежутка необходимо учесть следующее.

• Приблизительное количество простых чисел, не превосходящих определяется по асимптотической формуле:
  .
  Тогда примерное количество простых чисел в промежутке :
  .
  Задание слишком большого промежутка может привести к переполнению памяти, используемой браузером для вывода результатов.
• Первые 9592 простых чисел (до 99991) заложены в памяти программы. Остальные вычисляются колесным методом.
• Время вычислений растет с увеличением значений исследуемых натуральных чисел, входящих в промежуток .
• Калькулятор позволяет выполнять расчеты с использованием длинной арифметики при N₂ >9007199254740991. Однако время, затраченное на исследование одного натурального числа, сильно увеличивается, и составляет около 1 секунды для чисел, не сильно превышающих 9007199254740991.
• Теоретически, максимально возможное значение равно 81129638414606663681390495662081.

Дополнительные настройки

Число столбцов таблицы

Если ввести значение 0, то число столбцов таблицы рассчитывается автоматически.

Порядок колеса N

При фильтрации колесным методом, из ряда натуральных чисел удаляются элементы, делящиеся без остатка на первые N простых чисел.
См. Колесный метод фильтрации простых чисел

Задержка τ для отображения хода вычислений

Если время расчета превышает 1 секунду, то, после полной обработки исследуемого числа, происходит остановка расчетов, чтобы браузер отобразил текущие результаты во всплывающем окне хода вычислений. Через промежуток времени τ исследования чисел возобновляются. Если браузер не успевает показать прогресс вычислений, то можно увеличить τ, чтобы дать больше времени на отображения обработанных результатов. Прерывание расчетов происходит только после полной обработки текущего числа. До тех пор, пока этого не произойдет, изменений в окне хода вычислений не будет. Поэтому при расчете больших чисел возможно увеличение времени между обновлениями в окне хода вычислений.

Применяемый метод поиска простых чисел

Стандартный метод и его оптимизация

Пусть мы хотим найти все простые числа из промежутка . Самое легкое – взять каждое натуральное число из этого промежутка: , и проверить, является ли оно простым. Для этого нужно найти остатки от деления числа на все натуральные числа , не превышающие . Если все остатки не равны нулю, то число простое. Если хотя бы один остаток равен нулю: , то делится на . Поэтому не является простым.

Можно сократить объем вычислений, если в качестве перебирать не все натуральные числа, а только простые. Тогда для исследования числа нам потребуется вычислить не более остатков . Недостатком такой оптимизации является то, что для этого нужно хранить в памяти компьютера значений простых чисел , не превосходящих . Этот метод позволяет сократить объем вычислений, но при больших требуется большой объем памяти, что может привести к существенному снижению производительности вычислительной машины.

В этом калькуляторе использован другой способ оптимизации вычислений, основанный на фильтрации рядов и . Так, все четные числа, кроме двойки, не являются простыми. Поэтому из рядов и можно исключить четные числа. Тогда объем вычислений сократится более чем в два раза. Но также можно исключить числа, которые делятся на 3, 5, и так далее. Такая фильтрация выполняется с помощью колесного метода.

Колесный метод фильтрации простых чисел

Колесный метод – это метод построения ряда натуральных чисел, из которого исключены числа, делящиеся без остатка на первые простых чисел .
Числа, образующие колесо – это первые простых чисел .
Порядок колеса – это число первых простых чисел , образующих колесо.
Примориал – это произведение первых простых чисел:
.
Спицы колеса – Это множество натуральных чисел, каждое из которых меньше примориала, и не делится без остатка ни на одно число множества :
.
Число спиц в колесе определяется по формуле:
.

Элементы ряда определяются по формуле:
(1)   .
Таким образом, для построения колесным методом отфильтрованного ряда, содержащего все простые числа, мы выполняем следующие шаги.
1) Выбираем порядок колеса .
2) Определяем значения спиц .
3) Определяем значения элементов ряда по формуле (1).
4) Добавляем к ряду числа, образующие колесо, .

Пример. Для имеем.
Числа, образующие колесо: .
Примориал: .
Число спиц колеса: .
Значения спиц:

.
Прибавляя к ним примориал, мы получим значения элементов следующего оборота колеса. И так далее, последовательно прибавляя к новым значениям примориал, получаем элементы ряда натуральных чисел, из которых исключены элементы, делящиеся на 2,3,5,7.
Доля чисел, прошедших фильтр равна доле чисел в колесе:
.
Таким образом, используя колесный метод с , из ряда натуральных чисел мы убираем 77,14% чисел, которые делятся на 2, 3, 5, 7 и, следовательно, не являются простыми.

Эффективность колесного метода

Чем меньше доля чисел, прошедших фильтр, тем меньше операций нам нужно выполнить для получения списка простых чисел в заданном промежутке. Эта доля уменьшается при увеличении порядка колеса. Однако увеличение порядка приводит к увеличению числа спиц и, следовательно, к увеличению занимаемого ими объема памяти. Оказывается, что с ростом , доля чисел, прошедших фильтр снижается незначительно, в то время как объем занимаемой памяти растет очень сильно, быстрее экспоненты. Для выполнения расчетов, наиболее подходящими, являются значения порядка колеса от 4 до 6, .

В приведенной ниже таблице приведены значения числа спиц и доли чисел в колесе при разных значениях порядка .

Использованная литература.
Поиск простых чисел. Учебные материалы по информатике для школьников при мехмате 54 школы г. Москвы.

Автор: Олег Одинцов.     Опубликовано: 26-08-2022