Программирование циклов, цикл do while - Пример 2

Пример 2. Составить программу определения наибольшего общего делителя (НОД) двух натуральных чисел.

Решение.

Наибольший общий делитель двух натуральных чисел — это самое большое натуральное число, на которое они делятся. Например, у чисел 12 и 18 наибольшие делители: 2, 3, 6. наибольшим общим делителем является число 6. Это записывается так:

НОД(12, 18) = 6.

Идея алгоритма Евклида для нахождения НОД основана на том свойстве, что если M>N, то

НОД(M, N) = НОД(M-N, N).

Иначе говоря, НОД двух натуральных чисел равен НОД их положительной разности и меньшего числа.

Sub Евклид()
Dim M, N, NOD
 
M = Cells(1, 2)
N = Cells(2, 2)
 
While M <> N
 
If M > N Then
M = M - N
Else
N = N - M
End If
Wend
 
NOD = M
Cells(3, 2).Value = NOD
 
End Sub