ООО "Бизнескоп Консалтинг"
Математик-программист
УДК 511
Актуальность. Наиболее актуальным в теории чисел представляется поиск алгоритмов определения простоты числа за приемлемое время. Над этой сложнейшей проблемой математики работают уже много столетий по настоящее время. С появлением мощных вычислительных средств задача получила свое второе рождение, т.к. появилась возможность разработки и реализации современных алгоритмов поиска простых чисел.
Цели и задачи. Предложить алгоритм решета для поиска простых чисел с более высокой скоростью вычислений за счет уменьшения операций при решении квадратных уравнений составленных при помощи квадратичных форм.
Введение. Для поиска простых чисел, меньших некоторого заданного предела, математики используют, так называемый, метод решета простых чисел, суть которого состоит в вычеркивании (фильтрации) из натурального ряда составных чисел. Самым древним из всех методов считается Решето Эратосфена, который последовательно отфильтровывает все составные числа, кратные определенным простым на предыдущих этапах. Для реализации Решета Эратосфена разработаны различные алгоритмы, в частности, линейный [1]. Для оценки алгоритмов используют понятие вычислительной сложности, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Решето Эратосфена имеет вычислительную сложность , оцениваемую функцией O(nlog(logn)). Следует также выделить среди наиболее известных алгоритмов Решето Сундарама [2], оцениваемого по функции вычислительной сложности O(nlogn), и многочисленные модификации Решета Эратосфена, например [3], а также другие современные методы, так или иначе, основанные на построении решета простых чисел, например, методом исключений [4]. Однако они по вычислительной сложности принципиально не превосходят Решета Эратосфена. В настоящее время одним из самых быстрых алгоритмов определения простых чисел из массива чисел натурального ряда является Решето Аткина-Бернштайна [5] с вычислительной сложностью O(n). Основная идея алгоритма Решета Аткина-Бернштайна состоит в определении сравнения чисел по модулю 60 и в использовании неприводимых квадратичных форм, т.е. представлении чисел в виде ax²+by² в соответствии с теоремами Эйлера и Ферма. Основными недостатками Решета Аткина-Бернштайна является то, что использование рядов чисел по классу вычетов модулю 60 не позволяет использовать квадратичные формы с другими коэффициентами, нежели a=3 или a=4, а b=1 или b=-1, что практически и приводит к составлению для поиска решений квадратных уравнений достаточно громоздких матричных таблиц.
Предлагаемый способ позволяет значительно уменьшить количество операций при решении квадратных уравнений за счет расширения типов числовых рядов, обеспечивающее применение для каждого ряда квадратичной формы с повышающими коэффициентами.
Теоретическое обоснование. В десятичной системе исчисления натуральное число P записывается в виде
где
r - цифра соответствующего разряда числа,
а также записывается в виде краткой формы записи
Простое число, принадлежащее натуральному ряду, обладает двумя очевидными свойствами, легко проверяемыми по следующим признакам:
- по цифре единичного разряда r0 (последней цифре числа или по правому символу числа), которая не может быть четной и равной 0, 2, 4, 6, 8, иначе бы число по известному признаку делимости имело бы делитель равный 2, а также нечетной равной 5, иначе число по известному признаку делимости имело бы делитель равный 5, следовательно
- по сумме цифр ri всех разрядов числа
которая не может делиться на 3, 6, 9 по известным признакам делимости, иначе число имело бы соответствующие делители, из чего следует, что цифровой корень s0 числа [6], который является последовательным суммированием цифр всех разрядов числа пока не останется одной цифры, например,
не может принимать значения, кратные 3, т.е.
Заметим, что цифровой корень s0 простого числа может быть равен исключительно цифрам периода 1/7 = 0.142857 142857…
Таким образом, имея только 4 варианта единичного разряда и 6 вариантов цифрового корня числа, которые можно вычислить алгоритмически очень быстро для любого количества цифр числа, простые числа можно разделить на 24 типа по числу сочетаний единичного разряда и цифрового корня. Для нахождения всех рассматриваемых типов простого числа докажем теорему.
Теорема 1. Остаток R от деления числа P на 90 равен числу умноженной на десять разности цифрового корня и цифры единичного разряда числа плюс цифра единичного разряда. Для доказательства, запишем первое из выше указанных свойств в виде
а второе из выше указанных свойств в виде
Увеличив обе части первого уравнения в 9, а второго - в 10 раз, получим два уравнения
Вычитая из первого уравнения второе, получим
или
где
что и требовалось доказать. Можно заключить, что остаток R состоит из числа десятков
и цифры r0 единичного разряда. Следует заметить, если s0 < r0 , то
Следовательно, кандидаты в простые числа из ряда натуральных чисел разделяются на 24 типа по модулю сравнения 90 или, так называемым, классам вычетов [8], которые определяются всеми возможными сочетаниями цифрового корня и последнего знака числа.
Для примера, вычислим один из типов числового ряда, содержащего простые числа:
пусть r0 = 1, а s0 = 8, тогда R = (8 - 1) * 10 +1 = 71
В результате определен один из типов простого числа в виде класса вычетов по модулю 90:
где k - неполное частное.
Все типы чисел в виде рядов по модулю 90, в которых содержатся простые числа (выделены жирным шрифтом), в сочетании s0 и r0 распределены в таблице 1 по строкам в столбцах 2 и 3 соответственно. В столбце 4 представлены остатки R при делении числа-кандидата на 90 для чисел меньших 1100. В столбцах 5 - 15 расположены по строкам 1 - 48 все типы исследуемых числовых рядов. Причем их число увеличено вдвое только для того, чтобы в дальнейшем (см. ниже) наглядно показать отличия рассматриваемого метода от предшествующих, в частности, метода Аткина-Бернштайна. Следует отметить, что для каждого из 24 сочетаний s0 и r0 в таблице 1 представлены ряды, распределенные по двум строкам в зависимости от четного или нечетного неполного частного k. Этот факт также влияет на дальнейшие теоретические рассуждения, для чего докажем еще одну теорему о быстром способе определения четности неполного частного k.
Теорема 2. Неполное частное k от деления числа на 90 является четным, если разность цифры r1 десятичного разряда числа и числа десятков d0 остатка R четна, и, наоборот, неполное частное k от деления числа на 90 является нечетным, если разность цифры r1 десятичного разряда числа и числа десятков d0 остатка R нечетна. Для доказательства запишем уравнение в виде
сократив в обеих частях уравнения r0 , и поделив обе части на 10 имеем
Откуда следует, что разность r1 - d0 четна только в том случае, когда 9k четно и, следовательно, k четно, а в противном случае k нечетно, что и требовалось доказать.
Таким образом, построено решето чисел-кандидатов в простые на основе элементарных начальных вычислений трех параметров s0, r0 и r1 - d0, которые создают основу для дальнейшего отсеивания не простых чисел.
Квадратичные формы. Следующий шаг отсеивания не простых чисел или распознавания простых чисел основан на использовании, так называемых, квадратичных форм. Основная идея алгоритма, разработанная еще Эйлером и Ферма [7], состоит в поиске параметров представления чисел P в виде уравнения
Число P = n является простым тогда и только тогда, когда количество решений указанного выше уравнения нечётно и само число не кратно никакому квадрату простого числа. Наилучший на сегодняшний день алгоритм Аткина-Бернштайна использует три квадратичных формы (первого, второго и третьего родов) для поиска простых чисел сравниваемых по модулю 60, а именно:
Все формы для 24 рассматриваемых новых типов чисел представлены в таблице 1 в столбце 15. Собственно говоря, поиск решения указанных уравнений и является наиболее трудоёмкой задачей в части количества вычислительных операций, а, следовательно, временных затрат. Непосредственно решение очень просто описывается алгоритмически и состоит в том, что строят двух координатную сетку по осям, на пересечении которых вычисляют числа квадратных уравнений. Несложно убедиться в том, что размер сетки равен
Решето Аткина-Бернштайна оперирует с тремя размерами сетки:
Использование для поиска простых чисел сравнений по модулю 90 с четными и нечетными неполными частными позволило рассматривать сетки квадратичных форм со значительно уменьшенными размерами (или другими словами - увеличенным шагом сетки), что позволило, в конечном счете, для целого ряда чисел значительно уменьшить количество операций при решении квадратичных уравнений. Полученные новые уравнения представлены в столбце 17 таблицы 1. При этом в столбце 18 таблицы 1 показан эффект от применения нового уравнения в части количества операций по сравнению с решетом Аткина-Бернштайна. Например, рассмотрим квадратичную форму, дающую наибольший двойной или 100%-ный эффект (см. таблицу 1, строки 4, 6, 7, 12, 13 и т.д.). В таблице 2 представлена матрица решений уравнения первого рода, которая применяется в алгоритме Аткина-Бернштайна. Очевидно, что если в указанном уравнении неизвестное y заменить на 2y, то получим новое уравнение квадратичной формы
решения которого представлены в таблице 3. Из сравнения таблиц 2 и 3 видно, что они соответствуют одним и тем же типам рассматриваемых чисел. Найденные единственные решения в обеих таблицах соответствуют простым числам, выделенным жирным шрифтом, т.к. их число нечетно и равно 1. Двойные решения, выделенные жирным и подчеркнутым шрифтом, соответствуют не простым числам, т.к. их число четно и равное 2. В таблицах также отмечено жирным зачеркнутым шрифтом решения, соответствующие составным числам, имеющим один из множителей квадрат простого 847 = 7 * 112. Поскольку таблица 1 имеет размер 29 на 17 для чисел меньших 900, а таблица 3 для тех же чисел имеет вдвое меньший размер 17 на 14, применение новой квадратичной формы существенно сокращает объем вычислений. Следует уточнить, что не для всех рядов чисел подобрана новая квадратичная форма, например, для рядов в строках 3, 15, 11, 14, 44, 46, 17, 24, 25, 32, 34, 39 таблицы 1 квадратичная форма соответствует форме Аткина-Бернштайна. Для указанных рядов преимущества нового уравнения нет. Но это только одна четверть всех рядов. Для всех остальных 3/4 рядов преимущества в виде объема вычисления квадратичных форм колеблется от 12% до 100%.
О решении квадратичных форм. Для подбора значений x и y квадратичной формы необходимо и достаточно установить верхний предел равный целому из
после чего, уменьшая указанный предел на единицу вычислить значения
определив число решений в целых числах, причем корень извлекается только только тогда, когда подкоренное выражение оканчивается на 2, 3, 5, 7 или 8. Очевидно, что количество операций не более
что и определяет, главным образом, вычислительную сложность алгоритма.
Описание алгоритма решета простых чисел. Алгоритм построения решета простых чисел состоит из следующих шагов:
Пример. Определим простоту одного из решета чисел Мерсенна [9]
Для этого:
-запишем правый символ r0 = 7
-запишем второй символ справа r1 = 4
- вычислим цифровой корень
-вычислим вычислим параметр четности
-выберем по параметрам s0-r0-d0 = 1-7-1 квадратичную форму
-подсчитаем целый верхний предел по аргументу квадратичной формы
-уменьшая каждый раз x на единицу вычислим аргумент
пропуская вычисления, если правый символ подкоренного выражения не соответствует
-получим единственное решение в целых числах
- не тратим время на поиск квадратов простых делителей числа P, т.к. числа Мерсенна их не имеют, во всяком случае, согласно известной гипотезе [10]
-делаем вывод, что исследуемое число P Мерсенна простое!
Научная новизна. Можно говорить о научной новизне метода в части теоретического обоснования представления рядов натуральных чисел, содержащих и простые числа, по классам вычетов по модулю 90, а также применение новых квадратичных форм с повышающими коэффициентами и методе их решения.
Заключение. Предложенный алгоритм поиска простых чисел методом математического решета или фильтрации оценивается по вычислительной сложности как
где a и b суть коэффициенты квадратичной формы определенных типов представлений чисел, что делает его наиболее быстрым среди предшествующих аналогов. В статье представлено теоретическое обоснование алгоритма, приведены основные примеры расчетов.
Приложение
Таблица 1. Распределение простых чисел и их квадратичных форм
Номер столбца |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
Номер строки |
s0 |
r0 |
R |
P = R + 90*k |
Уравнение Аткина |
Новое Уравнение |
Уменьшение операций |
||||||||||
1 |
1 |
1 |
1 |
|
181 |
|
361 |
|
541 |
|
721 |
|
901 |
|
p=3x2 + y2 |
p=5x2 + y2 |
29% |
2 |
|
91 |
|
271 |
|
451 |
|
631 |
|
811 |
|
991 |
p=4x2 + y2 |
p=4x2 + 3y2 |
73% |
||
3 |
3 |
73 |
|
253 |
|
433 |
|
613 |
|
793 |
|
973 |
|
p=4x2 + y2 |
p=4x2 + y2 |
0% |
|
4 |
|
163 |
|
343 |
|
523 |
|
703 |
|
883 |
|
1063 |
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
||
5 |
7 |
37 |
|
217 |
|
397 |
|
577 |
|
757 |
|
937 |
|
p=4x2 + y2 |
p=4x2 + y2 |
0% |
|
6 |
|
127 |
|
307 |
|
487 |
|
667 |
|
847 |
|
1027 |
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
||
7 |
9 |
19 |
|
199 |
|
379 |
|
559 |
|
739 |
|
919 |
|
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
|
8 |
|
109 |
|
289 |
|
469 |
|
649 |
|
829 |
|
1009 |
p=4x2 + y2 |
p=5x2 + y2 |
12% |
||
9 |
4 |
1 |
31 |
|
211 |
|
391 |
|
571 |
|
751 |
|
931 |
|
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
10 |
|
121 |
|
301 |
|
481 |
|
661 |
|
841 |
|
1021 |
p=4x2 + y2 |
p=5x2 + y2 |
12% |
||
11 |
3 |
13 |
|
193 |
|
373 |
|
553 |
|
733 |
|
913 |
|
p=4x2 + y2 |
p=4x2 + y2 |
0% |
|
12 |
|
103 |
|
283 |
|
463 |
|
643 |
|
823 |
|
1003 |
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
||
13 |
7 |
67 |
|
247 |
|
427 |
|
607 |
|
787 |
|
967 |
|
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
|
14 |
|
157 |
|
337 |
|
517 |
|
697 |
|
877 |
|
1057 |
p=4x2 + y2 |
p=4x2 + y2 |
0% |
||
15 |
9 |
49 |
|
229 |
|
409 |
|
589 |
|
769 |
|
949 |
|
p=4x2 + y2 |
p=5x2 + y2 |
12% |
|
16 |
|
139 |
|
319 |
|
499 |
|
679 |
|
859 |
|
1039 |
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
||
17 |
2 |
1 |
11 |
|
191 |
|
371 |
|
551 |
|
731 |
|
911 |
|
p=3x2 - y2 |
p=3x2 - y2 |
0% |
18 |
|
101 |
|
281 |
|
461 |
|
641 |
|
821 |
|
1001 |
p=4x2 + y2 |
p=5x2 + y2 |
12% |
||
19 |
3 |
83 |
|
263 |
|
443 |
|
623 |
|
803 |
|
983 |
|
p=3x2 - y2 |
p=5x2 + 3y2 |
37% |
|
20 |
|
173 |
|
353 |
|
533 |
|
713 |
|
893 |
|
1073 |
p=4x2 + y2 |
p=5x2 + 3y2 |
94% |
||
21 |
7 |
47 |
|
227 |
|
407 |
|
587 |
|
767 |
|
947 |
|
p=3x2 - y2 |
p=5x2 + 3y2 |
37% |
|
22 |
|
137 |
|
317 |
|
497 |
|
677 |
|
857 |
|
1037 |
p=4x2 + y2 |
p=5x2 + 3y2 |
94% |
||
23 |
9 |
29 |
|
209 |
|
389 |
|
569 |
|
749 |
|
929 |
|
p=4x2 + y2 |
p=5x2 + y2 |
12% |
|
24 |
|
119 |
|
299 |
|
479 |
|
659 |
|
839 |
|
1019 |
p=3x2 - y2 |
p=3x2 - y2 |
0% |
||
25 |
8 |
1 |
71 |
|
251 |
|
431 |
|
611 |
|
791 |
|
971 |
|
p=3x2 - y2 |
p=3x2 - y2 |
0% |
26 |
|
161 |
|
341 |
|
521 |
|
701 |
|
881 |
|
1061 |
p=4x2 + y2 |
p=5x2 + y2 |
12% |
||
27 |
3 |
53 |
|
233 |
|
413 |
|
593 |
|
773 |
|
953 |
|
p=4x2 + y2 |
p=5x2 + 3y2 |
94% |
|
28 |
|
143 |
|
323 |
|
503 |
|
683 |
|
863 |
|
1043 |
p=3x2 - y2 |
p=5x2 + 3y2 |
37% |
||
29 |
7 |
17 |
|
197 |
|
377 |
|
557 |
|
737 |
|
917 |
|
p=4x2 + y2 |
p=5x2 + 3y2 |
94% |
|
30 |
|
107 |
|
287 |
|
467 |
|
647 |
|
827 |
|
1007 |
p=3x2 - y2 |
p=5x2 + 3y2 |
37% |
||
31 |
9 |
89 |
|
269 |
|
449 |
|
629 |
|
809 |
|
989 |
|
p=4x2 + y2 |
p=5x2 + y2 |
12% |
|
32 |
|
179 |
|
359 |
|
539 |
|
719 |
|
899 |
|
1079 |
p=3x2 - y2 |
p=3x2 - y2 |
0% |
||
33 |
5 |
1 |
41 |
|
221 |
|
401 |
|
581 |
|
761 |
|
941 |
|
p=4x2 + y2 |
p=5x2 + y2 |
12% |
34 |
|
131 |
|
311 |
|
491 |
|
671 |
|
851 |
|
1031 |
p=3x2 - y2 |
p=3x2 - y2 |
0% |
||
35 |
3 |
23 |
|
203 |
|
383 |
|
563 |
|
743 |
|
923 |
|
p=3x2 - y2 |
p=5x2 + 3y2 |
37% |
|
36 |
|
113 |
|
293 |
|
473 |
|
653 |
|
833 |
|
1013 |
p=4x2 + y2 |
p=5x2 + 3y2 |
94% |
||
37 |
7 |
77 |
|
257 |
|
437 |
|
617 |
|
797 |
|
977 |
|
p=4x2 + y2 |
p=5x2 + 3y2 |
94% |
|
38 |
|
167 |
|
347 |
|
527 |
|
707 |
|
887 |
|
1067 |
p=3x2 - y2 |
p=5x2 + 3y2 |
37% |
||
39 |
9 |
59 |
|
239 |
|
419 |
|
599 |
|
779 |
|
959 |
|
p=3x2 - y2 |
p=3x2 - y2 |
0% |
|
40 |
|
149 |
|
329 |
|
509 |
|
689 |
|
869 |
|
1049 |
p=4x2 + y2 |
p=5x2 + y2 |
12% |
||
41 |
7 |
1 |
61 |
|
241 |
|
421 |
|
601 |
|
781 |
|
961 |
|
p=4x2 + y2 |
p=5x2 + y2 |
12% |
42 |
|
151 |
|
331 |
|
511 |
|
691 |
|
871 |
|
1051 |
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
||
43 |
3 |
43 |
|
223 |
|
403 |
|
583 |
|
763 |
|
943 |
|
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
|
44 |
|
133 |
|
313 |
|
493 |
|
673 |
|
853 |
|
1033 |
p=4x2 + y2 |
p=4x2 + y2 |
0% |
||
45 |
7 |
7 |
|
187 |
|
367 |
|
547 |
|
727 |
|
907 |
|
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
|
46 |
|
97 |
|
277 |
|
457 |
|
637 |
|
817 |
|
997 |
p=4x2 + y2 |
p=4x2 + y2 |
0% |
||
47 |
9 |
79 |
|
259 |
|
439 |
|
619 |
|
799 |
|
979 |
|
p=3x2 + y2 |
p=4x2 + 3y2 |
100% |
|
48 |
|
169 |
|
349 |
|
529 |
|
709 |
|
889 |
|
1069 |
p=4x2 + y2 |
p=5x2 + y2 |
12% |
Таблица 2. Решения квадратичных уравнений Актина-Бернштайна
X Y |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
1 |
4 |
13 |
28 |
49 |
76 |
109 |
148 |
193 |
244 |
301 |
364 |
433 |
508 |
589 |
676 |
769 |
868 |
2 |
7 |
16 |
31 |
52 |
79 |
112 |
151 |
196 |
247 |
304 |
367 |
436 |
511 |
592 |
679 |
772 |
871 |
3 |
12 |
21 |
36 |
57 |
84 |
117 |
156 |
201 |
252 |
309 |
372 |
441 |
516 |
597 |
684 |
777 |
|
4 |
19 |
28 |
43 |
64 |
91 |
124 |
163 |
208 |
259 |
316 |
379 |
448 |
523 |
604 |
691 |
784 |
|
5 |
28 |
37 |
52 |
73 |
100 |
133 |
172 |
217 |
268 |
325 |
388 |
457 |
532 |
613 |
700 |
793 |
|
6 |
39 |
48 |
63 |
84 |
111 |
144 |
183 |
228 |
279 |
336 |
399 |
468 |
543 |
624 |
711 |
804 |
|
7 |
52 |
61 |
76 |
97 |
124 |
157 |
196 |
241 |
292 |
349 |
412 |
481 |
556 |
637 |
724 |
817 |
|
8 |
67 |
76 |
91 |
112 |
139 |
172 |
211 |
256 |
307 |
364 |
427 |
496 |
571 |
652 |
739 |
832 |
|
9 |
84 |
93 |
108 |
129 |
156 |
189 |
228 |
273 |
324 |
381 |
444 |
513 |
588 |
669 |
756 |
849 |
|
10 |
103 |
112 |
127 |
148 |
175 |
208 |
247 |
292 |
343 |
400 |
463 |
532 |
607 |
688 |
775 |
868 |
|
11 |
124 |
133 |
148 |
169 |
196 |
229 |
268 |
313 |
364 |
421 |
484 |
553 |
628 |
709 |
796 |
||
12 |
147 |
156 |
171 |
192 |
219 |
252 |
291 |
336 |
387 |
444 |
507 |
576 |
651 |
732 |
819 |
||
13 |
172 |
181 |
196 |
217 |
244 |
277 |
316 |
361 |
412 |
469 |
532 |
601 |
676 |
757 |
844 |
||
14 |
199 |
208 |
223 |
244 |
271 |
304 |
343 |
388 |
439 |
496 |
559 |
628 |
703 |
784 |
871 |
||
15 |
228 |
237 |
252 |
273 |
300 |
333 |
372 |
417 |
468 |
525 |
588 |
657 |
732 |
813 |
|||
16 |
259 |
268 |
283 |
304 |
331 |
364 |
403 |
448 |
499 |
556 |
619 |
688 |
763 |
844 |
|||
17 |
292 |
301 |
316 |
337 |
364 |
397 |
436 |
481 |
532 |
589 |
652 |
721 |
796 |
||||
18 |
327 |
336 |
351 |
372 |
399 |
432 |
471 |
516 |
567 |
624 |
687 |
756 |
831 |
||||
19 |
364 |
373 |
388 |
409 |
436 |
469 |
508 |
553 |
604 |
661 |
724 |
793 |
868 |
||||
20 |
403 |
412 |
427 |
448 |
475 |
508 |
547 |
592 |
643 |
700 |
763 |
832 |
|||||
21 |
444 |
453 |
468 |
489 |
516 |
549 |
588 |
633 |
684 |
741 |
804 |
||||||
22 |
487 |
496 |
511 |
532 |
559 |
592 |
631 |
676 |
727 |
784 |
847 |
||||||
23 |
532 |
541 |
556 |
577 |
604 |
637 |
676 |
721 |
772 |
829 |
|||||||
24 |
579 |
588 |
603 |
624 |
651 |
684 |
723 |
768 |
819 |
||||||||
25 |
628 |
637 |
652 |
673 |
700 |
733 |
772 |
817 |
868 |
||||||||
26 |
679 |
688 |
703 |
724 |
751 |
784 |
823 |
868 |
|||||||||
27 |
732 |
741 |
756 |
777 |
804 |
837 |
|||||||||||
28 |
787 |
796 |
811 |
832 |
859 |
||||||||||||
29 |
844 |
853 |
868 |
Таблица 3. Решения квадратичных уравнений нового вида
X Y |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
1 |
7 |
19 |
39 |
67 |
103 |
147 |
199 |
259 |
327 |
403 |
487 |
579 |
679 |
787 |
2 |
16 |
28 |
48 |
76 |
112 |
156 |
208 |
268 |
336 |
412 |
496 |
588 |
688 |
796 |
3 |
31 |
43 |
63 |
91 |
127 |
171 |
223 |
283 |
351 |
427 |
511 |
603 |
703 |
811 |
4 |
52 |
64 |
84 |
112 |
148 |
192 |
244 |
304 |
372 |
448 |
532 |
624 |
724 |
832 |
5 |
79 |
91 |
111 |
139 |
175 |
219 |
271 |
331 |
399 |
475 |
559 |
651 |
751 |
859 |
6 |
112 |
124 |
144 |
172 |
208 |
252 |
304 |
364 |
432 |
508 |
592 |
684 |
784 |
|
7 |
151 |
163 |
183 |
211 |
247 |
291 |
343 |
403 |
471 |
547 |
631 |
723 |
823 |
|
8 |
196 |
208 |
228 |
256 |
292 |
336 |
388 |
448 |
516 |
592 |
676 |
768 |
868 |
|
9 |
247 |
259 |
279 |
307 |
343 |
387 |
439 |
499 |
567 |
643 |
727 |
819 |
||
10 |
304 |
316 |
336 |
364 |
400 |
444 |
496 |
556 |
624 |
700 |
784 |
|||
11 |
367 |
379 |
399 |
427 |
463 |
507 |
559 |
619 |
687 |
763 |
847 |
|||
12 |
436 |
448 |
468 |
496 |
532 |
576 |
628 |
688 |
756 |
832 |
||||
13 |
511 |
523 |
543 |
571 |
607 |
651 |
703 |
763 |
831 |
|||||
14 |
592 |
604 |
624 |
652 |
688 |
732 |
784 |
844 |
||||||
15 |
679 |
691 |
711 |
739 |
775 |
819 |
871 |
|||||||
16 |
772 |
784 |
804 |
832 |
868 |
|||||||||
17 |
871 |
Рецензии:
23.02.2018, 22:38 Поплавская Лидия Андреевна
Рецензия: На сегодня существует множество алгоритмов генерации простых чисел определенного размера, получивших свое второе дыхание с развитием компьютерной техники. Причем, все они являются модификацией либо следствием известных классических и неоклассических алгоритмов как отечественных, так и зарубежных авторов, обзор фундаментальных из которых в статье не коснулся. Единого алгоритма для определения всех простых чисел на сегодня не существует, также как и не существует анализа быстродействия известных и разрабатываемых алгоритмов, их сравнения в плане эффективности и целесообразности применения. Как правило, программисты создают, на их взгляд, более компактные алгоритмы нахождения простых чисел, в которых нуждается в данный момент разрабатываемый ими проект, не доказывая сходимость процесса и не прилагая научно-обоснованный расчет быстродействия и сравнения с существующими алгоритмами, что наблюдается и в статье автора. Тем не менее, изложенный автором метод имеет место быть. А вот о его широком применении, и, вообще, о применении в частности, рецензент сомневается. Также как и в вызове интереса к нему со стороны пользователей простых чисел. Полагаю, что в журнале данный материал может быть опубликован.
С уважением, Л.Поплавская
4.10.2018, 14:39 Соловьёв Виктор Григорьевич Отзыв: Уважаемый Вадим Григорьевич! Благодарю Вас за отзыв к моей статье, к которой Вы очень внимательно отнеслись, судя по Вашим замечаниям и предложениям. Я рад, что моя статья пользуется вниманием специалистов, т.к. в отличие от сомнения рецензента о широком применении алгоритмов статьи, только просмотров с момента публикации уже больше тысячи. Что касается Вашего предложения об использовании рядов по классам вычетов по модулю 900, то отмечу следующее: безусловно можно использовать подобные классы вычетов в общем случае 90*к, в том числе и 900. Однако, в предложенном мною методе, основанном на принципе Ферма-Эйлера-Аткина, быстродействие алгоритма существенно зависит, главным образом, от скорости решения квадратичной формы, подобранной по определенным признакам к исследуемому на простоту числу. В отличие от известного метода Аткина мне удалось в работе показать, что использование не 3, а в общем виде 5-ти квадратичных форм да с еще повышенными коэффициентами, позволяет увеличить быстродействие алгоритма. Похоже, что использование классов вычета по модулю 90 исчерпывает все виды квадратичных форм, включающих все простые числа. Пока - это моя гипотеза - о достаточности использования классов вычетов по модулю 90 для построения решета простых чисел. Но мои исследования показали, что при любых других классах вычетов все равно количество квадратичных форм простых чисел ограничено 5-тью мною найденными. Еще раз Вас благодарю. С уважением, Виктор Соловьёв |
5.10.2018, 9:27 Соловьёв Виктор Григорьевич Отзыв: Уважаемый Вадим Григорьевич! Ваши сомнения мне понятны и даже приятны, т.к. отвечая на Ваши вопросы и предложения, мне удастся найти определенные доказательства, о которых я порой и не предполагал. Что касается ответа на вопрос по быстродействию, то оно практически (очень незначительно) не зависит от выбора модуля сравнения, но напрямую зависит от скорости решения уравнения квадратичной формы, о чем я писал ранее. А вот применение модуля 30 создаст дополнительные проблемы следующего характера: числа сравнимые по одному и тому же модулю имеют разные квадратичные формы, например, 127 = 7 mod 30 и 277 = 7 mod 30, оба числа простые и одинаковые по модулю 30. Однако, первое число имеет коэффициенты квадратичной формы 4 и 3, а второе - 3 и 1. Т.е. при проверке на простоту мы должны искать различные квадратичные формы. В моей же работе показано, что числа одинаковые при сравнении по модулю относятся к одной той же группе квадратичных форм. С уважением, Виктор Григорьевич Соловьёв |