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

Каждое натуральное число, больше единицы, делится, по крайней мере, на два числа: на 1 и на само себя. Если ни на какое другое натуральное число нацело не делится, то оно называется простым, а если у него имеются, еще какие-то делители, то - составным.
К простым и составным не относится только 1
Простые и составные числа

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

f (n) = n2 + n + 17
y (n) = n2 – n + 41
Попробуем вместо n последовательно подставлять в формулу натуральные числа.
Например: f (1) = 19, f (2) =23, f (6) = 59, f (7) =73
Все эти числа являются простыми, но уже
f (16) = 289 = 172, т.е. получилось составное число.
у(1) = 41, у(2) = 43, у(3) = 47 - числа простые, но
у(41) = 1681 = 412 является составным числом.
Поиски формулы простого числа

Числа Мерсенна.
М(р) = 2р – 1, где р – простое число. Составим таблицу таких чисел.
М(11) = 2047 = 23 * 89 – число составное.
М(31) = 2 147 483 647 есть простое число
М(61) = 2 305 843 002 913 693 951 есть простое число
М(216 091) – простое число

Пьер Ферма
F(n) =
Карл Фридрих Гаусс установил, что правильный p-угольник для простого р можно построить при помощи циркуля и линейки тогда и только тогда, когда р есть простое число вида F(n).

Основная теорема арифметики.
Любое натуральное число А может быть представлено в виде произведения
А = р1е1 * р2е2 * р3е3 * … * рnen
где p – различные простые числа
и e – натуральные показатели степени.