Разложение натуральных чисел в произведение простых

ЧИСЛО, одно из основных понятий математики; зародилось в глубокой древности и постепенно расширялось и обобщалось. В связи со счетом отдельных предметов возникло понятие о целых положительных (натуральных) числах, а затем идея о безграничности натурального ряда чисел: 1, 2, 3, 4.... Задачи измерения длин, площадей и т. п., а также выделение долей именованных величин привели к понятию рационального (дробного) числа. Понятие об отрицательных числах возникло у индийцев в 6-11 вв. Потребность в точном выражении отношений величин (напр., отношение диагонали квадрата к его стороне) привела к введению иррациональных чисел, которые выражаются через рациональные числа лишь приближенно; рациональные и иррациональные числа составляют совокупность действительных чисел. Окончательное развитие теория действительных чисел получила лишь во 2-й пол. 19 в. в связи с потребностями математического анализа. В связи с решением квадратных и кубических уравнений в 16 в. были введены комплексные числа.

Простое число́ — это натуральное число, которое имеет ровно 2 различных делителя (только 1 и само себя). Все остальные числа, не равные единице, называются составными. Таким образом, все натуральные числа, за исключением единицы, разбиваются на простые и составные. Изучением свойств простых чисел занимается теория чисел. В теории колец простым числам соответствуют неприводимые элементы.

Последовательность простых чисел начинается с

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, …

Разложение натуральных чисел в произведение простых

Основная теорема арифметики утверждает, что каждое натуральное число, большее единицы (1), представимо в виде произведения простых чисел, причём единственным способом с точностью до порядка следования сомножителей. Таким образом, простые числа — «элемен-тарные строительные блоки» натуральных чисел.

Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. (Здесь и далее речь идёт о полиномиальной зависимости времени работы алгоритма от логарифма проверяемого числа, то есть от количества его цифр). На алгоритмической сложности задачи факторизации базируется криптосистема RSA.