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

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

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

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

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

Теперь введём понятие - ряд простых чисел. Ряд первый - числа определяются по формуле:

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

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

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

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

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

 Например:

5 x 5 x 5 = 125 = 6n - 1

7 x 7 x 7 = 343 = 6n + 1

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

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

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

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

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

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

При этом поиск исключений простых чисел в первом ряду по формуле (6n - 1)(6k - 1) упрощается, так как исходное число всегда оканчивается на 5: 25, 55, 85, 115 и т. д..

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

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

(6n - 1) = 77

6n = 78

n = 13

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

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

36nk + 6n - 1 = 77

36nk + 6n - 6k = 78

6 (6nk + n - k) = 78

6nk + n - k = 13

n = 2, k = 1

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

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

Следующая формула позволит нам определить исключения из простых чисел на любом интервале рядов  простых чисел:

6na ± a

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

a- простое число.

Пример: n=1       a=5

6 x 1 x 5 ± 5 = 25; 35

n=1      a=7

6 x 1 x 7 ± 7 = 35; 49

n=1      a=11

6 x 1 x 11 ± 11 = 55; 77

и т.д.

При применении данной формулы в интервале от 0 до 1000,1000 и т.д. мы в несколько действий определим простые числа на данном отрезке.

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