Простые числа

Простые числа — это натуральные числа, большие 1, которые имеют ровно два натуральных делителя (то есть делятся только на 1 и на себя). Числа, которые имеют больше двух делителей, называются составными; число 1 не считается ни простым, ни составным.

Теорема Евклида. Простых чисел в натуральном ряду существует бесконечно много.

Первые простые числа: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, …
(Список простых чисел)

Разложение составных чисел на простые множители[]

Одной из важных задач является задача представления составного числа в виде произведения простых множителей.

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

Такое произведение называется разложением составного числа на простые множители.

Чтобы разложить число на простые множители, применяется несложный алгоритм: в ряду простых чисел подбирается по порядку такое число, которое является делителем заданного, затем подбирается наименьший простой делитель для частного и так далее (пример: 132 = 2 • 66 = 2 • 2 • 33 = 2 • 2 • 3 • 11). Как видно из основной теоремы арифметики, конечный результат не зависит от способа разложения числа.

Поиск простых чисел[]

Чтобы найти все простые числа в натуральном ряду от 1 до некоторого числа $N$ , можно применить один из существующих алгоритмов. Самым известным из них является «решето Эратосфена».

Алгоритм определения простых чисел методом решета Эратосфена:

выписать все натуральные числа от 2 до $N$ ;
выбрав первое простое число 2, вычеркнуть все числа кратные 2;
выбрав из следующих чисел первое, которое ещё не зачёркнуто, вычеркнуть все кратные числа, большие его;
выполнять пункт 3, пока это возможно.

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

Как проверить число на простоту?[]

Чтобы определить, является ли заданное число $M$ простым или составным, следует проверить, существует ли простое число, меньшее $M$ и являющееся делителем $M$ . Это можно сделать, перебирая по очереди все числа от 2 до $M$ .

Также перебор делителей можно существенно упростить, если воспользоваться утверждением: если среди натуральных чисел, не превосходящих $\sqrt{M}$ , ни одно не является делителем $M$ , то $M$ — простое число. Это правило позволяет ограничить перебор возможных делителей числом, равным целой части $\sqrt{M}$ (например, сделать вывод о простоте числа 79 можно, проверив все возможные делители до $[\sqrt{79}]$ = 8, а не до 78, как было бы при полном переборе).

Формулы для простых чисел[]

Поиск формулы, которая могла бы отделить простые числа от составных — одна из старейших задач теории чисел. В 18 веке от Р.Х. Леонард Эйлер указал многочлен $n^2 - n + 41$ , который при всех целых значениях $n$ от 0 до 40 даёт простые числа.

Примером формулы, которая охватывает все простые числа, может служить выражение
$f(n) = [\frac{1}{1 + \{\frac{(n-1)!+1}{n}\}}] - [\frac{1}{n}]$ ,
значение которого равно 1 при простом $n$ и 0 в остальных случаях.

Очень простые числа[]

очень простые числа — это числа получаемые следующей операцией: составляем последовательность из простых чисел и даём каждому простому числу номер места среди простых чисел а затем оставляем только те простые числа номера мест которых являются тоже простыми числами

первые очень простые числа — 3 5 11 17 31 41 59 67 83 и 109

Особенности простых чисел[]

2[]

2 это наименьшее простое число
2 это единственное чётное число являющиеся простым
2 это Единственное Сверх составное число и Практичное Число
это первое простое число в записи которого попадается цифра 2

3[]

Наименьшее очень простое число
единственное треугольное простое число
это первое простое число в записи которого попадается цифра 3

5[]

это первое простое число в записи которого попадается цифра 5
5 это Единственное Простое число с Цифрой 5, потому что Другие кратные 5 не простые числа.

7[]

наибольшее простое ровное число
это первое простое число в записи которого попадается цифра 7

11[]

Наибольшее простое число которое нельзя представить в виде суммы 2 составных чисел (все простые числа до 11 также нельзя представить в виде суммы 2 составных чисел)
в десятичной системе исчисления это первое число не являющиеся цифрой которое является простым
Между 11 и 7 (предыдущее простое число) чисел 3 — это первый случай отрезка из 3 цифр где не попадаются простые числа
это первое простое число в записи которого попадается цифра 1
Это Первое Простое Число в Записи которого Цифры повторяются и идут вместе

13[]

наименьшее простое число которое можно представить в виде суммы 2 составных чисел: 4+9=13 (все последующие простые числа также можно представить в виде суммы 2 составных чисел)

19[]

это первое простое число в записи которого попадается цифра 9

29[]

Между 29 и 23 (предыдущее простое число) всего чисел 5 — это первый случай отрезка из 5 чисел где не попадаются простые числа

41[]

это первое простое число в записи которого попадается цифра 4

61[]

это первое простое число в записи которого попадается цифра 6

83[]

это первое простое число в записи которого попадается цифра 8

97[]

Между 97 и 89 (предыдущее простое число) всего чисел 7 — это первый случай отрезка из 7 чисел где не попадаются простые числа
97 это единственное простое число от 91 до 100
97 это наибольшее простое двухзначное число

101[]

это первое простое трёхзначное число
это первое простое число в записи которого попадается цифра 0

В десятичной системе исчисления[]

Простые числа которые больше 5 могут заканчиваться только на цифры: 1 3 7 и 9
2 это единственное простое число начинающиеся на цифру: 2
5 это единственное простое число начинающиеся на цифру: 5
не существует ни единого простого числа которое заканчивается на цифры: 4 6 и 8
первый отрезок чисел из 10 чисел в котором не попадаются простые числа — 201-210