Евклид, цифры числа и делимость

Содержание и основные понятия

Числовые алгоритмы строятся из небольшого набора кирпичей: %, //, цикла и аккуратной границы перебора.
суть и практика
8 класс
ОГЭ №6
ОГЭ №16
ЕГЭ №25
01
Как это устроено
Числовые алгоритмы строятся на точном домене: какие числа допустимы, как определяется ответ для 0 и 1, где заканчивается перебор.
Цифры.
Для неотрицательного n: n % 10 берёт последнюю цифру, n // 10 удаляет её.
НОД.
Евклид заменяет (a, b) на (b, a % b), пока b не станет 0.
Делитель.
d — делитель n, если n % d == 0.
Квадратный корень.
Если n составно, у него есть делитель не больше sqrt(n).
02
Один пример в исполнении
Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.
Для проверки простоты числа
n
достаточно искать делитель от 2 до
isqrt(n)
включительно.
math.isqrt
возвращает целую часть квадратного корня без погрешности float. Числа 0 и 1 не простые; это должно быть явно отражено до цикла. Алгоритм Евклида обычно предполагает неотрицательные аргументы, а знак результата НОД договорённо делают неотрицательным.
Карта алгоритма
Читай слева направо, затем запускай код.
1
Начало
2
a = 84, b = 30
3
Заменить (a, b) на (b, a % b)
4
Сохранить новую пару
5
Вывести пару
03
Запомнить
Обработай n < 2 до перебора делителей.
Для полного квадрата граница isqrt(n) должна проверяться.
Проверь НОД равных чисел и случай, когда второе число уже равно нулю.
Синтаксис этой страницы
from math import isqrt
Импортирует целый квадратный корень из стандартного модуля math.
isqrt(n)
Возвращает floor(sqrt(n)) для неотрицательного n.
range(2, isqrt(n) + 1)
Включает целую границу проверки делителей.
%
Проверяет отсутствие остатка при делении.
while b: a, b = b, a % b
Компактная форма алгоритма Евклида для НОД.
int(input())
Читает целое число.
print
Выводит ответ или логическую метку.