Вычисление наибольших общих делителей

Найти наибольшие общие делители (НОД) для множества пар чисел.

Пусть пользователь будет вводить пары чисел, а на экран будут выводиться наибольшие общие делители этих чисел. В таком случае программу можно организовать следующим образом.

В основной ветке программы будет цикл, в теле которого будут

запрашиваться два числа,
вызываться функция для вычисления наибольшего общего делителя,
возвращаемый функцией результат выводиться на экран.

Условие прекращения работы цикла основной программы — ввод пользователем двух нулей.

НОД будет вычисляться в функции, которая будет получать два числа, а возвращать их НОД. Алгоритм нахождения НОД может быть следующим. Пока оба числа не равны нулю, находить остаток от деления большего числа на меньшее и присваивать его переменной, где хранилось большее число. После цикла сложить значения обоих переменных, — это и есть НОД.

На самом деле НОД содержится только в одной переменной, а вторая имеет нулевое значение (это условие окончания цикла). Однако нам неизвестно какая из двух содержит 0, поэтому проще их сложить, чем это выяснять.

Почему НОД можно определить таким способом (следует знать, что он не единственный)? Представим, что у нас два числа: 18 и 12. Остаток от деления 18 на 12 будет 6. Далее имеется два числа 12 и 6. Остаток от деления первого на второе равен 0. Он записывается на место числа 12. Получаем 0 и 6. Таким образом 12 делится нацело на 6, а вот как пояснить логически, что и 18 на него должно делиться?

Pascal



var a, b: word;

 

function gcd(c, d: word): word;

    begin

        while (c <> 0) and (d <> 0) do

            if c > d then

                c := c mod d

            else

                d := d mod c;

        gcd := c + d;

    end;

 

begin

    repeat

        write('Two numbers: ');

        readln(a,b);

        writeln('GCD: ', gcd(a,b));

    until (a = 0) and (b = 0);

end.





Two numbers: 56 18

GCD: 2

Two numbers: 196 144

GCD: 4

Two numbers: 305 809

GCD: 1

Two numbers: 810 3220

GCD: 10

Two numbers: 15000 10500

GCD: 1500

Two numbers: 0 200

GCD: 200

Two numbers: 0 0

GCD: 0

Язык Си



#include < stdio.h>

int gcd (int, int);

 

main() {

    int a, b;

    do {

        printf("Two numbers: ");

        scanf("%d%d", &a, &b);

        printf("GCD: %d\n", gcd(a,b));

    } while (a != 0 || b != 0);

}

 

int gcd(int c, int d) {

    while (c != 0 && d != 0) {

        if (c > d) c = c % d;

        else d = d % c;

    }

    return c + d;

}

Python



def gcd(c,d):

    while c != 0 and d != 0:

        if c > d:

            c %= d

        else:

            d %= c

    return c + d

 

a = b = 1

while a != 0 or b != 0:

    a = input("Two numbers: ")

    a = a.split()

    b = int(a[1])

    a = int(a[0])

    print("GCD:", gcd(a,b))

КуМир



алг 

нач

  цел а, б

  нц

    вывод "Введите два целых числа: "

    ввод а, б

    вывод "НОД = ", НОД(а,б), нс

  кц_при а = 0 и б = 0

кон

 

алг цел НОД (цел а, цел б)

нач

  цел в, г

  в := а

  г := б

  нц пока в <> 0 и г <> 0

    если в > г то в := mod(в,г)

     иначе г := mod(г,в)

    все

  кц

  знач := в + г

кон

Basic-256



do

	print "Введите два числа:"

	input a

	input b

	gosub gcd

until a = 0 and b = 0

end

 

gcd:

	c = a

	d = b

	while c<>0 and d<>0

		if c>d then

			c = c % d

		else 

			d = d % c

		endif

	endwhile

	print "НОД = " + (c+d)

return