36

Что такое Простое число? Плииз!

29 августа 2021

Что такое Простое число? Плииз!

категория: математика



94

Просто е число — это натуральное число, имеющее ровно два натуральных делителя: 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 (см. Список простых чисел для первых 500 простых). Натуральное число, имеющее больше двух делителей, называется составным. Таким образом, все натуральные числа, за исключением единицы, разбиваются на простые и составные. Разложение натуральных чисел в произведение простыхОсновная теорема арифметики утверждает, что каждое натуральное число, большее единицы (1), представимо в виде произведения простых чисел, причем единственным способом (с точностью до порядка следования сомножителей). Таким образом, простые числа — «элементарные строительные блоки» натуральных чисел. Представление натурального числа в виде произведения простых называется разложением на простые или факторизацией числа. На настоящий момент неизвестно полиномиальных алгоритмов факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. (Здесь и далее речь идет о полиномиальной зависимости времени работы алгоритма от логарифма проверяемого числа, то есть от количества его цифр). На алгоритмической сложности задачи факторизации базируется криптосистема RSA. Тесты простоты

Знаете ответ?


Есть интересный вопрос? Задайте его нашему сообществу, у нас наверняка найдется ответ!
Делитесь опытом и знаниями, зарабатывайте награды и репутацию, заводите новых интересных друзей!
Задавайте интересные вопросы, давайте качественные ответы и зарабатывайте деньги. Подробнее...