Извлечение корня из большого числа
Мы будем говорить сейчас только о случае, когда результат извлечения корня квадратного – целое число
Будем раскладывать число на простые множители.
Итак,
Поэтому
Случай 2
Пусть нам нужно вычислить
Пытаемся разложить на простые множители… Действовать так же, как описано выше, неудобно.
На число нацело не делится (не является четным)… На нацело не делится (сумма цифр не кратна )… На нацело не делится (последняя цифра – не и не )… На нацело не делится, на не делится, на не делится… Долго нам так перебирать все простые числа?
Будем рассуждать несколько иначе.
Мы понимаем, что
то есть
или
Мы сузили круг поиска. Теперь перебираем числа от до . Причем ясно, что раз последняя цифра числа – то останавливаться стоит на вариантах или – только эти числа при возведении в квадрат дадут последнюю цифру
Ну и тут уже, конечно, мы останавливаемся на Действительно,