Почему при проверке на простоту перебирают значения только до квадратного корня?

#алгоритм #математика

Часто задачи на определение простоты числа решают по такому алгоритму - перебирают
все числа начиная с 2 и пытаются разделить проверяемое число на каждое, пока не встретится
нулевой остаток. Если встретился- значит число не простое.

Но перебор ведут до квадратного корня из проверяемого числа. И я никак не пойму,
почему это так? Почему делитель не может встретиться среди чисел больше квадратного
корня от проверяемого? 
    

Ответы

Ответ 1

Если число не простое, то оно имеет как минимум два множителя, которые должны быть
меньше(либо равны) корня из исходного числа, иначе бы их произведение было бы больше
оного, поэтому нет смысла перебирать стоящие далее числа.