RUS  ENG
Полная версия
ЖУРНАЛЫ // Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика // Архив

Вестн. Астрахан. гос. техн. ун-та. Сер. управление, вычисл. техн. информ., 2017, номер 3, страницы 48–64 (Mi vagtu492)

Эта публикация цитируется в 2 статьях

КОМПЬЮТЕРНОЕ ОБЕСПЕЧЕНИЕ И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА

Распределение простых и составных чисел и их алгоритмические приложения

С. И. Чермидов

Кубанский государственный университет

Аннотация: На базе множества чисел вида $\Theta=\{6k\pm1/k\in N\}$, где $N$ — множество всех натуральных чисел, являющихся полугруппой относительно операции умножения, приводятся методы определения и распределения простых чисел, составных чисел, простых чисел близнецов и составных чисел близнецов, не имеющих делителей $2$ и $3$ в $N$. Дано вычисление точного числа простых чисел в заданном интервале. Предложен способ получения простых чисел по их порядковым номерам $n$ во множестве простых чисел $p\geqslant 5$, а также новый алгоритм нахождения и распределения простых чисел на базе замкнутости множества $\Theta$. Показано, что любое составное число $n\in\Theta$ представимо в виде произведения $(6x \pm 1) (6y\pm 1)$, где $x$, $y\in N$ являются натуральными решениями одного из четырех диофантовых уравнений: $P(x, y, \lambda) = 0: 6 xy \pm x \pm y - \lambda = 0$. Доказано, что если $\lambda$ есть параметр простых чисел близнецов, то ни одно из диофантовых уравнений $P(x, y, \lambda) = 0$ не имеет решения. Приводится новый универсальный, детерминированный, полиномиальный и независимый тест, позволяющий проверить, являются ли числа вида $6\cdot k \pm 1$ простыми. Приведены алгоритмы распределения параметров простых чисел близнецов и параметров составных чисел близнецов, не делящихся на $2$ и $3$, даны варианты доказательств их бесконечного количества.

Ключевые слова: простые и составные числа, параметры простых чисел, диофантовы уравнения, простые числа близнецы, тест на простоту, алгоритм распределения параметров.

УДК: 511.1:004.056

Поступила в редакцию: 29.05.2017
Исправленный вариант: 14.07.2017

DOI: 10.24143/2072-9502-2017-3-48-64



© МИАН, 2024