Почему необходимо проверить значения до sqrt (n), чтобы определить делители числа

Question

Я искал наиболее эффективный способ определения делителей числа.Я нашел статью, в которой упоминалось, что вместо итерации с 1 upto n можно сократить общее время выполнения с помощью итерации с 1 upto sqrt(n), и, если предположить, 1<=k<=sqrt(n), а k - это делитель числа n,тогда другой делитель будет n/k.
Есть ли какое-либо математическое доказательство того, что нам нужно повторять только до sqrt(n)?

Answer 1

если у вас есть делитель d >sqrt(n), то его дополнительный делитель n/d будет меньше n/sqrt(n), что равно sqrt(n), поэтому вы уже найдете n/d к концу вашего алгоритма ипоэтому также n/(n/d), что просто d.