Разделы: Математика
Размещена 07.09.2016. Последняя правка: 05.09.2016.
Просмотров - 6436

Простые числа - алгоритм поиска

Саковцев Владимир Павлович

Предприниматель

Предприниматель

УДК 511

Простое число- это такое число, которое делится на единицу и само себя.

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

В 200 году до н.э. грек Эратосфен придумал алгоритм для поиска простых чисел под названием "Решето Эратосфена".

Следующие открытия в этой области были сделаны уже в 17 веке математиком Ферма. Он доказал гипотезу Альбера Жирара, что любое простое число вида 4n+1 можно записать в виде суммы двух квадратов, сформулировал теорему, что любое число можно представить в виде суммы четырех квадратов. Доказал малую теорему Ферма и т.д.

Актуальность.  В этой области математики работали такие ученые, как Эйлер, Люкас, Чебышев, Риман.

Однако в теории простых чисел имеется еще множество нерешенных вопросов, некоторым из которых сотни лет.[1]

По мере развития технического прогресса потребность в понимании таких вопросов, как:

 

• существует ли арифметическая прогрессия из последовательных простых чисел для любой заданной длины?
• бесконечно ли число наборов из трех последовательных простых чисел в арифметической прогрессии?
• содержит ли последовательность Фибоначчи бесконечное количество простых чисел? и т.д.

 

не уменьшается, а требует их решения.

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

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

Мы определили местонахождения простых чисел в ряду натуральных чисел. Далее методом исключения последних определили принадлежность чисел к простым или натуральным числам. 

Для более полного понимания сути вопроса , предлагаем рассмотреть следующую таблицу:

6	12	18	24	30	36	42	48	54	60	66	72	78	84	90	96	102
5	11	17	23	29	35	41	47	53	59	65	71	77	83	89	95	101
4	10	16	22	28	34	40	46	52	58	64	70	76	82	88	94	100
3	9	15	21	27	33	39	45	51	57	63	69	75	81	87	93	99
2	8	14	20	26	32	38	44	50	56	62	68	74	80	86	92	98
1	7	13	19	25	31	37	43	49	55	61	67	73	79	85	91	97

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

Как видно из таблицы,- простые числа расположены в этих двух рядах.

Введём понятие, - ряд простых чисел.

Ряд первый- числа определяются по формуле:

6n+1, где n- натуральное число.

Ряд пятый: 6n-1.

Однако, как видно,  в этих двух рядах расположены не только простые числа, но и натуральные. В первом ряду числа: 25,49,55,85,91 и т.д. В пятом ряду числа: 35,65,77,95 и т.д.

            Данные числа определяются следующим образом:

                        5×5=25                       7×11=77

                        5×7=35                       7×13=91

                        5×11=55                     5×17=85   и т.д.

Все натуральные числа, расположенные в рядах простых чисел, находятся путём произведения простых чисел.

Например:

                                                    5×5×5=125=6n-1

                                                    7×7×7=343=6n+1

                                                    7×11×13=1001=6n+1

Данные натуральные числа, расположенные в рядах простых чисел назовём исключениями. Исключения, расположенные в первом ряду простых чисел, находятся по формулам:

                                                   (6n-1)(6k-1),

                                                   (6n+1)(6k+1)

где n, k- натуральные числа.

Расположенные  в пятом ряду по формуле:

                                                    (6n-1)(6k+1)

При этом поиск простых чисел в ряде случаев упрощается чисто визуально, так как ряд чисел (исключений) оканчивается на 5: 25, 35, 55,  85, 115 и т. д..

Рассмотрим следующий пример:

Является ли число 77 простым? Определяем в каком ряду простых чисел находится число 77.                                                             

                                                    6n-1=77

                                                    6n=78

                                                    n=13

Оно находится в пятом ряду.

Далее проверяем не является ли это число исключением:

                                                  (6n-1)(6k+1)=77

                                                  36nk+6n-6k-1=77

                                                  36nk+6n-6k=78

                                                  6(6nk+n-k)=78

                                                  6nk+n-k=13

                                                  n=2, k=1

                                                  11×7=77

Число 77 не является простым числом.

Данные формулы удобны для поиска отдельных простых чисел.

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

1)                                               6n-1,- пятый ряд

                                                  6n+1,- первый ряд

Допустим, 6n-1 или 6n+1=а.

Тогда  (6n-1)(6n+1)=6na-a  или  6na+a

 или  6na±a,-  в комплексе, где а- простое число, n- натуральное. 

По данной формуле мы находим исключения сразу в двух рядах простых чмсел. Оставшиеся числа в рядах простых чисел являются простыми.

 2)  a²+6na-  поиск исключений в первом ряду простых чисел.

 

3)                                             6n-1=a

                                                6k+1=b,

a×b- поиск исключений в пятом ряду простых чисел. Оставшиеся числа в первом или пятом рядах простых чисел, являются простыми. 

Данные формулы удобны для поиска простых чисел в каждом отдельном ряду.

Допустим, у нас есть заданное число. Мы определяем в каком ряду находится это число, и затем используя ту или иную формулу, находим исключения.
                                               1) 6nа+а

                                               n=1, а=5
                                               6х5+5=25, 35
                                               n=1, а=7
                                               6х7+7=35,49
                                               n=1, а=11
                                               6х11+11= 55,77 и т.д.

                                               2) а²+6nа
                                               а=5, n=1
                                               25+30=55
                                               а=5,n=2
                                               25+60=85
                                               а=5,n=3
                                               25+90=115 и т.д.

                                               3) ахв
                                               а=5, в=7
                                               5х7=35
                                               а=11, в=7
                                               11х7=77 ит.д.
Поиск простых чисел по каждому ряду отдельно позволяет ускорить процесс поиска как одного числа, так и заданного ряда чисел.

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

В заключении отметим: в данной работе мы показали некоторые особенности простых чисел.

Первое - простые числа расположены в определённой последовательности или в рядах простых чисел.
Второе - все натуральные числа, расположенные в рядах простых чисел, находятся путём произведения простых чисел.
Третье - оставшиеся числа,-являются простыми числами. 

1. Яковлев А.Я. Леонард Эйлер (Серия "Люди науки")-М.: Просвещение, 1983. 79с.
2. Марти Гарднер. Математические досуги-М.: Мир, 1972. 496 с.
3. Энциклопедический словарь юного математика.-М.: Педагогика, 1989.

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

23.09.2016, 11:45 Игорь Холопов Олегович Отзыв: Это у вас и получилось решето. Сгруппировав все числа в 6 строк, мы в каждой строке получаем арифметическую прогрессию k+6n, где k=1,2,..,6. Среди всех k не имеют общих делителей>1 с 6 только 1 и 5. Соответственно, в 4 строках из 6 общие делители можно вынести за скобку, и, таким образом, эти строки почти полностью вычеркнуть из поиска. Почему почти? Обратите внимание на числа 2 и 3. Таким образом, вы немного лукавите, говоря, что простые числа расположены только в 2 строках из 6. Итак, мы вычеркнули приблизительно 4/6 всех чисел и у нас осталось их, грубо говоря, 0.333*бесконечность. Почему вы взяли 6 строк, а не 7? Потому что 6=2*3. Можно пойти дальше, и, вместо нагромождения формул, расписать всё на 2*3*5=30 строк. Это будет следующий шаг вашего решета. Легко убедиться, что в этот раз мы вычеркнем "почти" 22/30, и останется у нас примерно 0.267*бесконечность, то есть меньше, чем на предыдущем шаге. На третьем шаге мы распишем все наше множество N на 2*3*5*7=210 строк. Относительное количество строк, в которых есть простые числа, станет еще меньше. Но абсолютное их количество все равно будет бесконечность. И легче нам от этого не станет. Решето - это хороший способ выписывания последовательных простых чисел, но он не дает нам "формулу простого числа". Если Вам кажется, что через несколько шагов все простые числа окажутся в вашем решете, то это не так. Предлагаю самостоятельно найти последовательность, дающую долю чисел, среди которых остались простые, для i-го шага. И исследовать сходимость этой последовательности. Если же пытаться написать алгоритм с произвольным количеством шагов (то есть, с увеличением числа строк), то в итоге вы придете к тому же Эратосфену, только каким-то очень обходным путем. К тому же не забудьте про 1й столбец, в котором содержится целиком начало ряда простых чисел, и который в вашем решете требует отдельного рассмотрения.

26.09.2016, 12:38 Саковцев Владимир Павлович Отзыв: Игорь Олегович, ознакомился с вашим отзывом. К сожалению моей статьи он не касается. Я не ищу формулу простого числа, мне проще найти простые числа, определяя исключения в рядах простых чисел. Например: в интервале от 0 до 100 в рядах простых чисел находится 33 числа. Находим числа исключения в этих рядах. Их девять. 33-9=24 простых числа (кроме 2 и 3). Аналогичная ситуация и далее. Мы не нагромождаем количество строк на каждом шаге. Повторяем, строк с простыми числами,- две. При проверке простых чисел до 500 миллионов ошибки не было.Что же касается первого столбца, то давайте не будем проводить отдельного рассмотрения, а просто запомним эти простые числа (2 и 3). С уважением Владимир Саковцев.

27.09.2016, 7:00 Холопов Игорь Олегович Отзыв: Владимир Павлович, очень жаль, что вы не читали мой комментарий. Поскольку я вашу статью все-таки прочитал. "найти простые числа, определяя исключения в рядах простых чисел" - это решето. Но сказав А, нужно говорить В. Смысла в "одношаговом" решете, как у вас, - абсолютно никакого нет. Уменьшив число кандидатов в простые числа на две трети, мы не получим никакой прибыли, потому что их все равно бесконечность. С бесконечностями так не работают. С ними нужен алгоритм, который постоянно уменьшает число кандидатов, на каждом шаге. Я увидел вашу идею и предложил такой алгоритм. Но он плохой. Вот если бы по вашей идее можно было построить алгоритм, который ищет простые числа за время, меньшее, чем O(N), как у решета Аткина, это был бы прорыв. Но и то чисто теоретический, потому что запись ряда простых чисел - не самая главная задача в простых числах. Этот ряд известен до очень больших значений, и проще взять готовый, чем изобретать колесо. Гораздо важнее проверка простоты произвольного числа и его факторизация. Впрочем, ваши слова "строк с простыми числами,- две. При проверке простых чисел до 500 миллионов ошибки не было" говорят о том, что вы не понимаете, что делаете. Причем дважды. Во-первых, ошибки там, разумеется, нет, но для этого не нужно проверять 500 миллионов, достаточно показать, что прогрессия k+6n может содержать простые числа только при k=1 и k=5. А во вторых, 500 миллионов подтверждений (не в этом случае, а вообще) ничего не гарантируют.

28.09.2016, 6:52 Холопов Игорь Олегович Отзыв: Кстати, вдогонку - вот вчерашняя статья на гиктаймсе про очень крутую оптимизацию решета Эратосфена: https://geektimes.ru/post/280896/

19.11.2016, 14:25 Новиков Игорь Витальевич Отзыв: Добрый день, Владимир Павлович! Буду очень краток, но если заинтересую - пишите на почту i.vit.nov@yandex.ru Я разработал алгоритм поиска простого числа указанной длины на основе четырёх утверждений: 1. Первообразный корень g существует только для простых чисел. 2. Любое число W=P-1, где Р - простое число, можно разложить на простые множители. 3. Чтобы найти g, нужно последовательно разделить W на все свои простые множители, таким образом получаем необходимые для проверки показатели степени N1...Ni. 4. И если ни одно из значений (g в степени N1...i по модулю Р) не равно единице, а кроме того, g в степени (P-1)/2 по модулю Р равно Р-1, то говорят, что g является первообразным корнем Р. Таким образом, найдя g находим и Р. Осталось только подобрать множители так, чтобы их было ТРИ ШТУКИ: двойка, простое число до миллиарда (из таблицы) и большое простое число, полученное из предыдущего действия. Для быстрого отсева составных чисел используем четвёрку. Если при возведении её в степень (P-1)/2 по модулю Р, где Р - проверяемое нечётное число, получается не единица, то число точно составное. Числа g и Р образуют кольцо ключей (числа от 1 до Р-1), которые используются в криптографии, поскольку по ключу К (результату вычисления) практически невозможно за полиномиальное время узнать его номер (показатель степени). Написано много, но способ очень быстрый: 300-битное число находит за полчаса (640 бит - за 9 часов), кроме того находит первообразный корень. Первая минута времени отдана на создание решета Эрастофена до миллиарда.

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