Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?
Вакпрофи. Публикация статей ВАК, Scopus
Научные направления
Поделиться:
Статья опубликована в №54 (февраль) 2018
Разделы: Математика
Размещена 22.02.2018. Последняя правка: 04.10.2018.

Алгоритм решета простых чисел

Соловьёв Виктор Григорьевич

ООО "Бизнескоп Консалтинг"

Математик-программист

Аннотация:
Рассматривается оригинальный алгоритм построения решета для поиска простых чисел, основанный на анализе квадратичными формами рядов натуральных чисел, являющимися классами вычетов по модулю 90, значение которого теоретически обосновано, исходя из очевидных свойств простых чисел. Отличительной особенностью алгоритма является построение рядов чисел, содержащих простые числа, по признакам и сочетаниям исключительно цифрового корня и двух крайних правых знаков числа, что позволяет избежать трудоемких сравнений чисел по модулю, что, в свою очередь, практически обеспечивает возможность подбора к каждому ряду квадратичных форм с повышенными коэффициентами. В результате по сравнению с известными алгоритмами значительно уменьшено количество операций при расчете решета простых чисел, что делает предлагаемый алгоритм одним из самых быстрых в части затрат времени на вычисления.


Abstract:
The original algorithm of sieve development for the prime numbers search is considered. The algorithm is based on analysis by quadratic forms of series of counting numbers that are residue classes modulo 90, which value is theoretically justified on the basis of prime numbers’ obvious properties. A differential characteristic of the algorithm is the development of numbers’ series containing prime numbers, solely based on signs and combinations of the digital root and two extreme right-hand numbers. It allows avoiding laborious comparisons of numbers modulo, which, in turn, makes it possible to select quadratic forms for each series with increased coefficients. As a result, quantity of operations for calculation of the prime numbers’ sieve in comparison with common algorithms is significantly reduced, that makes proposed algorithm time optimal.


Ключевые слова:
простые числа; решето простых чисел; решето Аткина-Бернштайна; квадратичные формы; цифровой корень; сравнения по модулю

Keywords:
prime numbers; sieve of prime numbers; Atkin-Bernstein sieve; quadratic forms; digital root; congruence modulo


УДК 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, что практически и приводит к составлению для поиска решений квадратных уравнений достаточно громоздких матричных таблиц.

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

Теоретическое обоснование. В десятичной системе исчисления натуральное число записывается в виде
 

где



 r - цифра соответствующего разряда числа,

а также записывается в виде краткой формы записи




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

- по цифре единичного разряда r0 (последней цифре числа или по правому символу числа), которая не может быть четной и равной 0, 2,  4,  6,  8, иначе бы число по известному признаку делимости имело бы делитель равный 2,  а также нечетной равной 5, иначе число по известному признаку делимости имело бы делитель равный 5, следовательно


- по  сумме цифр ri  всех разрядов числа

которая не может делиться на 3, 6, 9 по известным признакам делимости, иначе число имело бы соответствующие делители, из чего следует, что цифровой корень s0 числа [6], который является последовательным суммированием цифр всех разрядов числа пока не останется одной цифры, например,



не может принимать значения, кратные 3, т.е.

Заметим, что цифровой корень sпростого числа может быть равен исключительно цифрам периода 1/7 = 0.142857 142857…

Таким образом, имея только 4 варианта единичного разряда и 6 вариантов цифрового корня числа, которые можно вычислить алгоритмически очень быстро для любого количества цифр числа, простые  числа можно разделить на 24 типа по числу сочетаний единичного разряда и цифрового корня. Для нахождения всех рассматриваемых типов простого числа докажем теорему.

Теорема 1. Остаток R от деления числа на 90 равен числу умноженной на десять разности цифрового корня и цифры единичного разряда числа плюс цифра единичного разряда. Для доказательства, запишем первое из выше указанных свойств в виде

а второе из выше указанных свойств в виде

Увеличив обе части первого уравнения в 9, а второго - в 10 раз, получим два уравнения



Вычитая из первого уравнения второе, получим



или


где 



 что и требовалось доказать. Можно заключить, что остаток R состоит из числа десятков 


и цифры r0 единичного разряда. Следует заметить, если  s0  <  r0 , то


Следовательно, кандидаты в простые числа из ряда натуральных чисел разделяются на 24 типа по модулю сравнения 90 или, так называемым, классам вычетов [8], которые определяются всеми возможными сочетаниями цифрового корня  и последнего знака числа.

Для примера, вычислим один из типов числового ряда, содержащего простые числа:

пусть r= 1, а s= 8,  тогда R = (8 - 1) * 10 +1 = 71

 
В результате определен один из типов простого числа в виде класса  вычетов по модулю 90:


где k - неполное частное.

Все типы чисел в виде рядов по модулю 90, в которых содержатся простые числа (выделены жирным шрифтом), в сочетании sи r0 распределены в таблице 1 по строкам в столбцах 2 и 3 соответственно. В столбце 4 представлены остатки  при делении числа-кандидата на 90 для чисел меньших 1100. В столбцах 5 - 15 расположены по строкам 1 - 48 все типы исследуемых числовых рядов. Причем их число увеличено вдвое только для того, чтобы в дальнейшем (см. ниже) наглядно показать  отличия рассматриваемого метода от предшествующих, в частности, метода Аткина-Бернштайна. Следует отметить, что для каждого из 24 сочетаний  sи rв таблице 1 представлены ряды, распределенные по двум строкам в зависимости от четного или нечетного неполного частного k. Этот факт также влияет на дальнейшие теоретические рассуждения, для чего докажем еще одну теорему о быстром способе определения четности неполного частного k.

Теорема 2. Неполное частное k от деления числа на 90 является четным, если разность цифры r1 десятичного разряда числа и числа десятков dостатка четна, и, наоборот, неполное частное k от деления числа на 90 является нечетным, если разность цифры  r1 десятичного разряда числа и числа десятков   dостатка нечетна. Для доказательства запишем уравнение в виде

 

сократив в обеих частях уравнения r0 , и поделив обе части на 10 имеем

 

Откуда следует, что разность r1 - d0 четна только в том случае, когда  9четно и, следовательно, k четно, а в противном случае k нечетно, что и требовалось доказать.

Таким образом, построено решето чисел-кандидатов в простые на основе элементарных начальных вычислений трех параметров s0,  r0 и r1 - d0, которые создают основу для дальнейшего отсеивания не простых чисел.

Квадратичные формы. Следующий шаг отсеивания не простых чисел или распознавания простых чисел основан на использовании, так называемых, квадратичных форм. Основная идея алгоритма, разработанная еще Эйлером и Ферма [7], состоит в поиске параметров представления чисел в виде  уравнения 



Число P = является простым тогда и только тогда, когда количество решений указанного выше уравнения нечётно и само число не кратно никакому квадрату простого числа. Наилучший на сегодняшний день алгоритм Аткина-Бернштайна использует три квадратичных формы (первого, второго и третьего родов) для поиска простых чисел сравниваемых по модулю 60, а именно:




Все формы для 24 рассматриваемых новых типов чисел представлены в таблице 1 в столбце 15. Собственно говоря, поиск решения указанных уравнений и является наиболее трудоёмкой задачей в части количества вычислительных операций, а, следовательно, временных затрат. Непосредственно решение очень просто описывается алгоритмически и состоит в том, что строят двух координатную сетку по осям, на пересечении которых  вычисляют числа квадратных уравнений. Несложно убедиться в том, что размер сетки равен

Решето Аткина-Бернштайна оперирует с тремя размерами сетки:



Использование для поиска простых чисел сравнений по модулю 90 с четными и нечетными неполными частными позволило рассматривать сетки квадратичных форм со значительно уменьшенными размерами (или другими словами - увеличенным шагом сетки), что позволило, в конечном счете, для целого ряда чисел значительно уменьшить количество операций при решении квадратичных уравнений. Полученные новые уравнения представлены в столбце 17 таблицы 1. При этом в столбце 18 таблицы 1 показан эффект от применения нового уравнения в части количества операций по сравнению с решетом Аткина-Бернштайна. Например, рассмотрим квадратичную форму, дающую наибольший  двойной или 100%-ный эффект (см. таблицу 1, строки 4,  6, 7, 12, 13 и т.д.). В таблице 2 представлена матрица решений уравнения первого рода, которая применяется в алгоритме Аткина-Бернштайна. Очевидно, что если в указанном уравнении неизвестное заменить на 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. Очевидно, что количество операций не более

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

Описание алгоритма решета простых чисел. Алгоритм построения решета простых чисел состоит из следующих шагов:

  • определяется правый символ rчисла и вычеркиваются все числа, которые не оканчиваются на 1, 3, 7, 9
  • вычисляется цифровой корень sчисла и вычеркиваются все числа,  цифровой корень которых  не равен 1, 4, 2, 8, 5, 7
  • вычисляется разность предпоследнего символа числа r1 и числа d0= s0  - r0 , по которой определяют параметр четности h=0 или нечетности h=1 неполного частного от деления числа на 90 (не выполняя операций вычисления остатка по модулю 90)
  • из оставшихся объявляются простыми (остальные вычеркиваются) все числа, которые содержат цифровой корень s0, правый символ r0  и параметр четности h равныe соответственно s0-r0-h
    • 2-1-0 , 2-9-1, 8-1-0, 8-9-1, 5-1-1, 5-9-0 и нечетным количеством решений уравнения 3x² - y² = n
    • 1-3-0, 1-7-0, 4-3-0, 4-7-1, 7-3-1, 7-7-1 и нечетным количеством решений уравнения  4x² + y² = n
    • 1-1-0, 1-9-1, 4-1-1, 4-9-0, 2-1-1, 2-9-0, 8-1-1, 8-9-0, 5-1-0, 5-9-1, 7-1-0, 7-9-1 и нечетным количеством решений уравнения 5x² + y² = n
    • 1-1-1, 1-3-1, 1-7-1, 1-9-0, 4-1-0, 4-3-1, 4-7-0, 4-9-1, 7-1-1, 7-3-0, 7-7-0, 7-9-0 и нечетным количеством решений уравнения 4x² + 3y² = n
    • 2-3, 2-7, 8-3, 8-7, 5-3, 5-7 (независимо от четности) и нечетным количество решений уравнения 5x² + 3y² = n
  • вычеркиваются числа, кратные квадратам простых чисел, начиная с 7.
  • все оставшиеся числа составляют решето простых

Пример. Определим простоту одного из  решета чисел Мерсенна [9]


Для этого:

-запишем правый символ r0 = 7

-запишем второй символ справа r1 = 4

- вычислим цифровой корень

-вычислим вычислим параметр четности

-выберем по параметрам s0-r0-d0 = 1-7-1 квадратичную форму

-подсчитаем целый верхний предел по аргументу  квадратичной формы
 

-уменьшая каждый раз на единицу вычислим аргумент


пропуская вычисления, если правый символ подкоренного выражения не соответствует

-получим единственное решение в целых числах

- не тратим время на поиск квадратов простых делителей числа P, т.к. числа Мерсенна их не имеют, во всяком случае, согласно известной гипотезе [10]

-делаем вывод, что исследуемое число P Мерсенна  простое!

 

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

Заключение. Предложенный алгоритм поиска простых чисел методом математического решета или фильтрации оценивается по вычислительной сложности как


где a и суть коэффициенты квадратичной формы определенных типов представлений чисел, что делает его наиболее быстрым среди предшествующих аналогов. В статье представлено теоретическое обоснование алгоритма, приведены основные примеры расчетов.


Приложение

Таблица 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

                         

Библиографический список:

1. David Gries, Jayadev Misra. A Linear Sieve Algorithm for Finding Prime Numbers. 1978
2. V. Ramaswami Aiyar "Sundaram's Sieve for Prime Numbers". The Mathematics Student (Madras, India). ISSN 0025-5742. 1934
3. O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, Published online by Cambridge University Press 9 October 2008
4. Саковцев В.П. Простые числа - алгоритм поиска. Научно периодический электронный рецензируемый журнал SCI-ARTICLE.RU, сентябрь 2016
5. A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023—1030.
6. Ghannam, Talal (4 January 2011), The Mystery of Numbers: Revealed Through Their Digital Root, CreateSpace Publications, pp. 68–73, ISBN 978-1-4776-7841-1
7. Harold M. Edwars Fermat's Last Theorem. A genetic introduction to Algebraic Number Theory. Springer-Verlag New York Heidelberg Berlin, 1977
8. Виноградов И.М. Основы теории чисел. М.: Наука, 1972
9. Деза Е.И. Специальные числа натурального ряда. М.: ЛИБРИКОМ, 2011, с.95-97
10. Серпинский В. Что мы знаем и чего не знаем о простых числах. Перевод с польского И.Г.Мельникова. М.: ГИФМЛ, 1963, с.80




Рецензии:

23.02.2018, 22:38 Поплавская Лидия Андреевна
Рецензия: На сегодня существует множество алгоритмов генерации простых чисел определенного размера, получивших свое второе дыхание с развитием компьютерной техники. Причем, все они являются модификацией либо следствием известных классических и неоклассических алгоритмов как отечественных, так и зарубежных авторов, обзор фундаментальных из которых в статье не коснулся. Единого алгоритма для определения всех простых чисел на сегодня не существует, также как и не существует анализа быстродействия известных и разрабатываемых алгоритмов, их сравнения в плане эффективности и целесообразности применения. Как правило, программисты создают, на их взгляд, более компактные алгоритмы нахождения простых чисел, в которых нуждается в данный момент разрабатываемый ими проект, не доказывая сходимость процесса и не прилагая научно-обоснованный расчет быстродействия и сравнения с существующими алгоритмами, что наблюдается и в статье автора. Тем не менее, изложенный автором метод имеет место быть. А вот о его широком применении, и, вообще, о применении в частности, рецензент сомневается. Также как и в вызове интереса к нему со стороны пользователей простых чисел. Полагаю, что в журнале данный материал может быть опубликован. С уважением, Л.Поплавская

24.02.2018 16:16 Ответ на рецензию автора Соловьёв Виктор Григорьевич:
Уважаемая Лидия Андреевна! Я благодарен Вам за положительный отзыв, позволяющий принять к публикации мою статью, несмотря на некоторые сомнения в части быстродействия и громоздкости моего алгоритма. Согласен с Вам, что не приведено научного обоснования быстродействия, потому что в этом случае я бы вышел далеко за рамки и размеры статьи. Однако, в статье я пишу о том, что усовершенствовал известный и один самых быстрых алгоритмов поиска простых чисел и для определенного по классу вычетов ряда мой алгоритм значительно превосходит известный, что и показано в таблицах и на примере. Думаю, что следующая моя работа, основанная на рецензируемой Вами, развенчает Ваши сомнения. Так же надеюсь, что работа все-таки будет интересна специалистам в области алгоритмов поиска простых чисел. С благодарностью, Виктор Григорьевич Соловьёв

12.03.2018, 21:49 Поплавская Лидия Андреевна
Рецензия: Уважаемый Виктор Григорьевич! Я бы выразилась следующим образом: "разложил на лопатки" один из быстрых алгоритмов поиска простых чисел. С небольшой модификацией. Но объем практической работы проделан достаточный. Полагаю, какое-то внимание Ваш материал все же привлечет. И статья имеет место на продление жизни. Рекомендую статью к опубликованию. Л.Поплавская
13.03.2018 10:10 Ответ на рецензию автора Соловьёв Виктор Григорьевич:
Уважаемая Лидия Андреевна! Вы подобрали достаточно точный фразеологизм, объясняющий суть моей статьи. Единственное, я бы уточнил по поводу "небольшой модификации", которая, на мой взгляд, все-таки существенна. Действительно, мне удалось математически доказать переход с модуля 60 в известном алгоритме на модуль 90 при подборе квадратичных форм, что позволило для целого класса чисел существенно увеличить коэффициенты, тем самым сократив затраты на количеству операций на решение уравнений. Еще раз благодарю Вас за положительную оценку моего труда. С уважением, Виктор Григорьевич Соловьёв



Комментарии пользователей:

3.10.2018, 14:57 Ремизов Вадим Григорьевич
Отзыв: Уважаемый Виктор Григорьевич! Хочу поделиться с Вами своими соображениями. Одной из древнейших проблем математики является поиск ряда простых чисел. Эта проблема очень время затратная, несмотря на использование современных компьютеров с огромным быстродействием. Самым древним методом считается Решето Эратосфена, то есть метод решета простых чисел, суть которого состоит в вычеркивании из натурального ряда составных чисел. В настоящее время одним из самых быстрых алгоритмов определения простых чисел из массива чисел натурального ряда является Решето Аткина-Бернштайна, который состоит в определении сравнения по модулю 60 и в использовании неприводимых квадратичных форм в соответствии с теоремами Эйлера и Ферма. Автором усовершенствован указанный метод, за счет оригинального алгоритма построения решета для поиска простых чисел, основанный на анализе квадратичными формами рядов натуральных чисел, являющимися классами вычетов по модулю 90. Как мне кажется, имеется возможность усовершенствования алгоритма поиска простых чисел по классам вычетов по модулю (2*2)(3*3)(5*5)=900. Алгоритм с этим модулем должен незначительно усложнить вывод уравнений метода, но должен еще больше повысить быстродействие алгоритма. С уважением, Вадим Григорьевич Ремизов


4.10.2018, 14:39 Соловьёв Виктор Григорьевич
Отзыв: Уважаемый Вадим Григорьевич! Благодарю Вас за отзыв к моей статье, к которой Вы очень внимательно отнеслись, судя по Вашим замечаниям и предложениям. Я рад, что моя статья пользуется вниманием специалистов, т.к. в отличие от сомнения рецензента о широком применении алгоритмов статьи, только просмотров с момента публикации уже больше тысячи. Что касается Вашего предложения об использовании рядов по классам вычетов по модулю 900, то отмечу следующее: безусловно можно использовать подобные классы вычетов в общем случае 90*к, в том числе и 900. Однако, в предложенном мною методе, основанном на принципе Ферма-Эйлера-Аткина, быстродействие алгоритма существенно зависит, главным образом, от скорости решения квадратичной формы, подобранной по определенным признакам к исследуемому на простоту числу. В отличие от известного метода Аткина мне удалось в работе показать, что использование не 3, а в общем виде 5-ти квадратичных форм да с еще повышенными коэффициентами, позволяет увеличить быстродействие алгоритма. Похоже, что использование классов вычета по модулю 90 исчерпывает все виды квадратичных форм, включающих все простые числа. Пока - это моя гипотеза - о достаточности использования классов вычетов по модулю 90 для построения решета простых чисел. Но мои исследования показали, что при любых других классах вычетов все равно количество квадратичных форм простых чисел ограничено 5-тью мною найденными. Еще раз Вас благодарю. С уважением, Виктор Соловьёв


4.10.2018, 17:29 Ремизов Вадим Григорьевич
Отзыв: Уважаемый Виктор Григорьевич! Я не знаю прав я или нет, я сомневаюсь. Но я думаю, что заслуживает рассмотрения и модуль равный 2*3*5=30. Не знаю насколько возрастает быстродействие алгоритма с увеличением модуля, но самый простой алгоритм основан на модуле 30, поэтому быстродействие алгоритмов надо сравнивать с алгоритмом по модулю 30. С уважением, Вадим Григорьевич Ремизов


5.10.2018, 9:27 Соловьёв Виктор Григорьевич
Отзыв: Уважаемый Вадим Григорьевич! Ваши сомнения мне понятны и даже приятны, т.к. отвечая на Ваши вопросы и предложения, мне удастся найти определенные доказательства, о которых я порой и не предполагал. Что касается ответа на вопрос по быстродействию, то оно практически (очень незначительно) не зависит от выбора модуля сравнения, но напрямую зависит от скорости решения уравнения квадратичной формы, о чем я писал ранее. А вот применение модуля 30 создаст дополнительные проблемы следующего характера: числа сравнимые по одному и тому же модулю имеют разные квадратичные формы, например, 127 = 7 mod 30 и 277 = 7 mod 30, оба числа простые и одинаковые по модулю 30. Однако, первое число имеет коэффициенты квадратичной формы 4 и 3, а второе - 3 и 1. Т.е. при проверке на простоту мы должны искать различные квадратичные формы. В моей же работе показано, что числа одинаковые при сравнении по модулю относятся к одной той же группе квадратичных форм. С уважением, Виктор Григорьевич Соловьёв


Оставить комментарий


 
 

Вверх