Формулювання. Дано два натуральних числа. Знайти їх найбільший спільний дільник.
Примітка: найбільшим спільним дільником (скорочено пишуть НОД) двох натуральних чисел m і n називається найбільший з їхніх спільних дільників. Позначення: НСД (m. N).
Примітка 2: загальним дільником двох натуральних чисел називається натуральне число, на яке натуральне число, яке є дільником обох цих чисел.
Наприклад, знайдемо НСД (12, 8):
Випишемо всі подільники числа 12: 1, 2, 3, 4, 6, 12;
Випишемо всі подільники числа 8: 1, 2, 4, 8;
Випишемо всі загальні дільники чисел 12 і 8: 1, 2, 4. З них найбільша кількість - 4. Це і є НОД чисел 12 і 8.
Рішення. Звичайно, при вирішенні ми не будемо виписувати подільники та вибирати потрібний. В принципі, її можна було б вирішити як задачу 15. почавши цикл з найменшого з двох заданих чисел (так як воно теж може бути НСД, наприклад, НСД (12, 4) = 4). Але ми скористаємося так званим алгоритмом Евкліда знаходження НСД, який виведений за допомогою математичних методів. У самому простому випадку для заданих чисел m і n він виглядає так:
1) Есліmнеравноn, перейти до кроку 2, в іншому випадку вивестіmі закінчити алгоритм;
3) Перейти на крок 1
Як бачимо, в кроці 2 більше з двох поточних чисел замінюється різницею більшого і меншого.
Наведемо приклад для чисел 12 і 8:
a. Так як 12> 8, замінимо 1 2 Перейти до 12 - 8 = 4;
b. Так як 8> 4, замінимо 8 на 8 - 4 = 4;
Чи не проводячи жодних міркувань над алгоритмом і не доводячи його коректності, переведемо його опис в ближчу для мови Pascal форму:
Алгоритм природною мовою:
2) Запуск циклу з передумовою m <>n. У циклі:
1. Якщо m> n. то змінної m присвоїти m -n. інакше змінної n привласнити n -m;