Можно ли создать алгоритм генерации простых чисел вида 4к + 1 и 4к -1?
ПрограммированиеМатематикаАлгоритмы
Во-первых, формулы для простых чисел существуют. Тут можно отметить результаты Матиясевича. Имеется его популярная статья и большая лекция, которую стоит послушать чтобы получить лучшее представление об этом вопросе.
Во-вторых, есть известная теорема Дирихле, которая гласит что в любой арифметической прогрессии первый член которой и разность — взаимно простые числа, содержится бесконечно простые числа.
Во-вторых, есть известная теорема Дирихле, которая гласит что в любой арифметической прогрессии первый член которой и разность — взаимно простые числа, содержится бесконечно простые числа.
Так что отвечая на ваш вопрос: мы можем выбрать множество чисел указанного вида, и среди них (по теореме Дирихле) есть бесконечно много простых. Ну а алгоритмов для проверки числа на простоту очень много.
Однако, если посмотреть на вопрос с более общих позиций, а именно задаться вопросом о существовании формул которые будут выдавать числа такого вида — то и тут есть возможности, например с использованием упомянутых результатов Матиясевича и других его последователей.
Однако, если посмотреть на вопрос с более общих позиций, а именно задаться вопросом о существовании формул которые будут выдавать числа такого вида — то и тут есть возможности, например с использованием упомянутых результатов Матиясевича и других его последователей.
Однако, если честно, у этих формул есть большой недостаток — их чудовищная сложность.
Автор удалил комментарий
Ответы на похожие вопросы
Можно ли создать алгоритм генерации простых чисел вида 4к + 1 и 4к -1? — 2 ответа, задан
Скажем, как самое простое, решето Эратосфена можно запустить не только по нечётным числам, но и по числам такого вида.
Другой вариант: использовать часть алгоритма решета Аткина https://ru.wikipedia.org/wiki/Решето_Аткина
Все числа, равные (по модулю 60) 1, 13, 17, 29, 37, 41, 49 или 53, имеют остаток от деления на 4, равный 1. Эти числа являются простыми тогда и только тогда, когда количество решений уравнения 4x² + y² = n нечётно и само число не кратно никакому квадрату простого числа.
Можно ли создать алгоритм генерации простых чисел вида 4к + 1 и 4к -1? — 2 ответа, задан
Первое простое число вида 4к + 1 есть 5, а первое простое число вида 4к -1 есть 3. Второе простое число вида 4к +1 есть 13, третье простое число вида 4к +1 есть 17 и так далее. второе простое число вида 4к -1 есть 7 и так далее.