Извлечение корня из большого числа

Итак, пусть нам во что-бы то ни стало (например,  при вычислении дискриминанта) нужно вычислить корень квадратный из $86436.$

Мы будем раскладывать число $86436$ на простые множители. Делим на $2,$ – получаем $43218;$ снова делим на $2,$ – получаем $21609.$ На $2$ больше нацело число не делится. Но так как сумма цифр делится на $3,$ то и само число делится на $3$ (вообще говоря, видно, что оно и на $9$ делится). $21609:3=7203$. Еще раз делим на $3,$ – получаем  $2401.$ $2401$ на $3$ нацело не делится. На пять не делится (не оканчивается цифрой $0$ или $5).$

Подозреваем делимость на $7.$ Действительно, $2401:7=343,$  а $343:7=49$, $49=7\cdot 7.$

Итак, $86436=2^2\cdot 3^2\cdot 7^4.$ Полный порядок!

Поэтому $\sqrt{86436}=\sqrt{(2\cdot 3\cdot 49)^2}=\sqrt{(294)^2}=294.$

Пусть нам нужно вычислить $\sqrt{1849}$. Действовать так же, как описано выше, неудобно. Пытаемся разложить на простые множители…

На $2$ число $1849$ нацело не делится (не является четным)…

На $3$ нацело не делится (сумма цифр не кратна $3$)…

На $5$ нацело не делится (последняя цифра – не $5$ и не $0$)…

На $7$ нацело не делится, на $11$ не делится, на $13$ не делится… Ну и долго нам так перебирать все простые числа?

Будем рассуждать несколько иначе.

Мы понимаем, что

$1600<1849<2500$,

то есть

$\sqrt{1600}<\sqrt{1849}<\sqrt{2500}$

или

$40<\sqrt{1849}<50$

Мы сузили круг поиска. Теперь перебираем числа от $41$ до $49.$ Причем ясно, что раз последняя цифра числа – $9,$ то останавливаться стоит на вариантах $43$ или $47,$ – только эти  числа при возведении в квадрат дадут последнюю цифру $9.$

Ну и тут уже, конечно, мы останавливаемся на $43.$ Действительно, $43^2=1849.$