➗Проверка на простост

Какво е просто число

Просто число е целое число, по-голямо или равно на 2, което няма делители, различни от 1 и самото себе си. Числа като 2, 3, 5, 7 и 11 са прости; 2 е единственото четно просто число.

Дали 1 е просто число

1 не е просто число. Простите числа се определят като целни числа, по-голяма или равни на 2. Ако 1 се включи в простите числа, свойството на простата факторизация – че всяко целое число може да бъде изразено като произведение на прости числа по единствен начин – няма да важи.

Как да разпознаете простите числа

За да определите дали целото число n е просто, последователно го делите на числа до √n; ако нито един не го дели равномерно, то е просто. Например 91 е делимо на 7, което е по-малко от √91 (приблизително 9,5), така че 91 не е просто.

• Метод на пробното деление：Методът на пробното деление дели n последователно на числа от 2 до √n, за да намери делители; при големи числа броят на делението става огромен.
• Тест на Милър–Рабин：Тестът на Милър–Рабин проверява остатъците на степени с няколко основи, за да намери доказателство, че числото не е просто; може да определи простотата на големи числа бързо.