Для меня проблема оценки делителя возникла, когда попыталься факторизовать большие числа. Простой перебор, как вы сами понимаете, не метод. Хотя формально обеспечивает 100% - ю достоверность результата. Значит следует делать скачки через определенный интервал чисел. Но произвольно выбирать интервал нельзя, можно проскочить искомый делитель. Вот и возникла задача - сформулировать оценку сверху наименьшего делителя. Почему сверху, а не снизу? Просто так легче реализовалось. Об оценке снизу я еще подумаю...
Сам алгоритм следующий: число

, которое должно быть заведомо больше или равно делителю

всегда можно указать, например
![$n=[\sqrt{N}]$ $n=[\sqrt{N}]$](https://dxdy-02.korotkov.co.uk/f/9/3/e/93e5754f67b8fbfe53397c268ff05bf482.png)
, дальше вычисляем интервал скачка, где точно нет делителя, обозначим его
![$a=[\frac{\sqrt{Nr}}m]-1$ $a=[\frac{\sqrt{Nr}}m]-1$](https://dxdy-03.korotkov.co.uk/f/6/0/5/605b965b0d84db4877be77b5ff452bc382.png)
. Число

точно не делитель, а вот

уже может быть делителем. Проверяем его, если это не делитель, то это число становится нашим новым

для которого строится свои

и

. Процедура снова повторяется. Только появление делителя процедуру прерывает.
Я не утверждаю, что это оптимальный алгоритм, но обращаю внимание - в алгоритме нет процедуры поиска простых чисел. И еще, искать делитель можно и на обычном калькуляторе, самое сложное действие - это извлечение квадратного корня.