Задача по СИ по нахождению НОД(наибольший общий делитель)
Задача: Заданы натуральные числа А и В. Составить программу для определения наибольшего общего делителя.
Наибольший общий делитель (НОД) мы будем находить с помощью простого алгоритма Евклида, вот он: если даны натуральные числа a и b и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД. Вообще другой алгоритм, более быстрый вы можете посмотреть на Википедии, тут я привел простой алгоритм:
Решение:
Исходный код:
#include<stdio.h>
#include<conio.h>
main()
{
int A, B; /* Объявляем целочисленные переменные*/
scanf("%d", &A); /* Вводим число с клавиатуры*/
scanf("%d", &B); /* Вводим число с клавиатуры*/
printf("A=%d, B=%d", A, B); /*Выводим на монитор введенное число*/
while (A!=0 && B!=0) /*Пока А и В не равняется нулю делать следующее*/
if (A>B) /*Если А больше В*/
A=A-B;
else /*Иначе*/
B=B-A;
if (A!=0)
printf ("\nNOD=%d\n", A); /*Выводим на монитор полученную сумму*/
else
printf ("\nNOD=%d\n", B); /*Выводим на монитор полученную сумму*/
getch(); /*Функция, чтобы при завершении программы результаты оставались на экране*/
return 0; /*Эта строка говорит о том, что программа завершилась корректна*/
}
Тестирование:
24 36
А=24, В=36
NOD 12