Теорема
Наименьший простой делитель составного числа а не превосходит √а.
Доказательство:
Пусть p – наименьший простой делитель числа а.Обозначим: d – дополнительным к p делитель числа а, т.е.a= p*d.
Докажем, что p≤d, если d – простое число, то p≤d, поскольку p – наименьший простой делитель числа а. Если же d – составное число, то у него в свою очередь, есть простой делитель. Обозначим его p1. Это число p1, будучи делителем числа d, является также делителем числа а по транзитивности отношения делимости. Значит,p≤p1, т.к. p – наименьший простой делитель а. В свою очередь, p1≤d, т.к. d делится на p1. Итак, p≤d и в случае составного d, поэтому p≤d в любом случае. Посколькуp≤d, то умножив обе части этого неравенства на p, и воспользовавшись монотонностью умножения, получаем, что
P2≤p*d.
Но d*p=a, значит, p2≤a, т.е. p≤√a, а это и требовалось доказать.
На практике чтобы узнать является ли число простым, достаточно проверять на делимость не все простые числа, меньшие этого числа, а все простые числа, меньшие или равные кв.корню этого числа.
