Проверка на първо число

Просто число е естествено число, по-голямо от 1, което няма други положителни делители освен 1 и самото себе си. Първите прости числа са 2, 3, 5, 7, 11, 13, 17, 19, 23, 29...

Не, 1 не се смята за просто число. По дефиниция простото число трябва да е по-голямо от 1 и да има точно два различни положителни делителя (1 и самото то). Числото 1 има само един делител.

Да, 2 е единственото четно просто число. То се дели само на 1 и 2. Всички останали четни числа се делят на 2, така че не могат да бъдат прости.

Първичните числа са основополагащи в математиката и са от решаващо значение за съвременната криптография. Криптирането RSA, използвано за защита на онлайн трансакции, се основава на трудността при разделянето на големи числа на техните прости компоненти.

Съществуват безкрайно много прости числа, както е доказано от Евклид около 300 г. пр.н.е. Независимо колко голямо просто число откриете, винаги има по-голямо. Въпреки това с нарастването на числата простите числа стават все по-редки - само около 4% от числата, близки до един милион, са прости.

Към 2024 най-голямото известно просто число е 2^82,589,933 - 1, открито през 2018. Това число на Мерсен има 24,862,048 цифри. Нови рекордни прости числа се откриват чрез Great Internet Mersenne Prime Search (GIMPS) — проект за разпределени изчисления.

За малки числа проверете делимостта с прости числа до квадратен корен. Например, за да проверите дали 97 е просто число, проверете променливите числа до √97 ≈ 9,8 (така че проверете 2, 3, 5, 7). Тъй като 97 не се дели на нито едно от тези числа, то е просто.

Двойките прости числа са двойки прости числа, които се различават с 2, като (3,5), (5,7), (11,13), (17,19) и (29,31). Предположението за двойни числа предполага, че съществуват безкрайно много такива, но това остава недоказано въпреки вековете математически изследвания.

Всяко съставно число може да бъде изразено еднозначно като произведение на първични числа (Фундаментална теорема на аритметиката). Факторизацията на прости числа се използва при опростяване на дроби, намиране на GCD/LCM, криптография и решаване на много математически задачи. Например, 60 = 2^2 × 3 × 5.

Първичните числа на Мерсен имат формата 2^p - 1, където p също е просто число. Примери за това са 3 (2^2-1), 7 (2^3-1) и 31 (2^5-1). Те са значими при намирането на големи първични числа и имат връзка с идеалните числа. Известни са само 51 първични числа на Мерсен.