Методы решения физико-математических задач

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

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

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

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

  –     ?

⚙ Настройки
  ?
  ?
  ?

Результаты вычислений

Затраченное время: 0 мс. Число найденных чисел: 1229.

Таблица простых чисел в промежутке от 1 до 10000

💾 Сохранить в файл
23571113171923293137
414347535961677173798389
97101103107109113127131137139149151
157163167173179181191193197199211223
227229233239241251257263269271277281
283293307311313317331337347349353359
367373379383389397401409419421431433
439443449457461463467479487491499503
509521523541547557563569571577587593
599601607613617619631641643647653659
661673677683691701709719727733739743
751757761769773787797809811821823827
829839853857859863877881883887907911
919929937941947953967971977983991997
100910131019102110311033103910491051106110631069
108710911093109711031109111711231129115111531163
117111811187119312011213121712231229123112371249
125912771279128312891291129713011303130713191321
132713611367137313811399140914231427142914331439
144714511453145914711481148314871489149314991511
152315311543154915531559156715711579158315971601
160716091613161916211627163716571663166716691693
169716991709172117231733174117471753175917771783
178717891801181118231831184718611867187118731877
187918891901190719131931193319491951197319791987
199319971999200320112017202720292039205320632069
208120832087208920992111211321292131213721412143
215321612179220322072213222122372239224322512267
226922732281228722932297230923112333233923412347
235123572371237723812383238923932399241124172423
243724412447245924672473247725032521253125392543
254925512557257925912593260926172621263326472657
265926632671267726832687268926932699270727112713
271927292731274127492753276727772789279127972801
280328192833283728432851285728612879288728972903
290929172927293929532957296329692971299930013011
301930233037304130493061306730793083308931093119
312131373163316731693181318731913203320932173221
322932513253325732593271329933013307331333193323
332933313343334733593361337133733389339134073413
343334493457346134633467346934913499351135173527
352935333539354135473557355935713581358335933607
361336173623363136373643365936713673367736913697
370137093719372737333739376137673769377937933797
380338213823383338473851385338633877388138893907
391139173919392339293931394339473967398940014003
400740134019402140274049405140574073407940914093
409941114127412941334139415341574159417742014211
421742194229423142414243425342594261427142734283
428942974327433743394349435743634373439143974409
442144234441444744514457446344814483449345074513
451745194523454745494561456745834591459746034621
463746394643464946514657466346734679469147034721
472347294733475147594783478747894793479948014813
481748314861487148774889490349094919493149334937
494349514957496749694973498749934999500350095011
502150235039505150595077508150875099510151075113
511951475153516751715179518951975209522752315233
523752615273527952815297530353095323533353475351
538153875393539954075413541754195431543754415443
544954715477547954835501550355075519552155275531
555755635569557355815591562356395641564756515653
565756595669568356895693570157115717573757415743
574957795783579158015807581358215827583958435849
585158575861586758695879588158975903592359275939
595359815987600760116029603760436047605360676073
607960896091610161136121613161336143615161636173
619761996203621162176221622962476257626362696271
627762876299630163116317632363296337634363536359
636163676373637963896397642164276449645164696473
648164916521652965476551655365636569657165776581
659966076619663766536659666166736679668966916701
670367096719673367376761676367796781679167936803
682368276829683368416857686368696871688368996907
691169176947694969596961696769716977698369916997
700170137019702770397043705770697079710371097121
712771297151715971777187719372077211721372197229
723772437247725372837297730773097321733173337349
735173697393741174177433745174577459747774817487
748974997507751775237529753775417547754975597561
757375777583758975917603760776217639764376497669
767376817687769176997703771777237727774177537757
775977897793781778237829784178537867787378777879
788379017907791979277933793779497951796379938009
801180178039805380598069808180878089809381018111
811781238147816181678171817981918209821982218231
823382378243826382698273828782918293829783118317
832983538363836983778387838984198423842984318443
844784618467850185138521852785378539854385638573
858185978599860986238627862986418647866386698677
868186898693869987078713871987318737874187478753
876187798783880388078819882188318837883988498861
886388678887889389238929893389418951896389698971
899990019007901190139029904190439049905990679091
910391099127913391379151915791619173918191879199
920392099221922792399241925792779281928392939311
931993239337934193439349937193779391939794039413
941994219431943394379439946194639467947394799491
949795119521953395399547955195879601961396199623
962996319643964996619677967996899697971997219733
973997439749976797699781978797919803981198179829
983398399851985798599871988398879901990799239929
99319941994999679973

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Порядок колеса
Примориал
Число спиц
Доля чисел,
прошедших фильтр
1 2 1 0,5
2 6 2 0,3333
3 30 8 0,2667
4 210 48 0,2286
5 2 310 480 0,2078
6 30 030 5 760 0,1918
7 510 510 92 160 0,1805
8 9 699 690 1 658 880 0,1710
9 223 092 870 36 495 360 0,1636
10 6 469 693 230 1 021 870 080 0,1579

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

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

Меню