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

Числовые алгоритмы строятся из небольшого набора кирпичей: %, //, цикла и аккуратной границы перебора.

суть и практика8 классОГЭ №6ОГЭ №16ЕГЭ №25

Как это устроено

Числовые алгоритмы строятся на точном домене: какие числа допустимы, как определяется ответ для 0 и 1, где заканчивается перебор.

Цифры. Для неотрицательного n: n % 10 берёт последнюю цифру, n // 10 удаляет её.

НОД. Евклид заменяет (a, b) на (b, a % b), пока b не станет 0.

Делитель. d — делитель n, если n % d == 0.

Квадратный корень. Если n составно, у него есть делитель не больше sqrt(n).

Один пример в исполнении

Запусти короткую программу и переходи по строкам. Визуализатор показывает только код, текущую строку, переменные и вывод.

Для проверки простоты числа n достаточно искать делитель от 2 до isqrt(n) включительно. math.isqrt возвращает целую часть квадратного корня без погрешности float. Числа 0 и 1 не простые; это должно быть явно отражено до цикла. Алгоритм Евклида обычно предполагает неотрицательные аргументы, а знак результата НОД договорённо делают неотрицательным.

Карта алгоритмаЧитай слева направо, затем запускай код.

1Начало
2a = 84, b = 30
3Заменить (a, b) на (b, a % b)
4Сохранить новую пару
5Вывести пару

Запомнить

Обработай 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

Выводит ответ или логическую метку.