Вычислить наибольший общий делитель (НОД) двух натуральных чисел

@egesavran · Регистрация: 27.09.2020

Author24 — интернет-сервис помощи студентам

Вычислить наибольший общий делитель (НОД) натуральных чисел а, b.

@мама Стифлера · 03.10.2020, 01:50

C++ (Qt)

#include <iostream>
using namespace std;
int main()
{
    int a, b, i;
    cin >> a >> b;
    if (b != a && (b%a == 0 || a%b == 0)) {
        cout << (a<b ? a : b) << endl;
        return 0;
    }
    if (a>b) i = b/2;
    else i = a/2;
    for(; i>=0; i--)
        if(a%i==0 && b%i==0) {
            cout << i << endl;   
            break;
        }
    return 0;
}

@igorrr37 · 03.10.2020, 03:25

C++

#include <iostream>
#include <numeric>
 
 
int main()
{
    int a = 49, b = 21;
    std::cout << std::gcd(a, b);
}

@NQUARE · 03.10.2020, 11:53

C++

int Nod(int a, int b) {
    while (a && b) {
        if (a >= b) a %= b;
        else b %= a;
    }
    return a | b;
}

@мама Стифлера · 03.10.2020, 13:35

Спасибо Евклиду, на проч позабыл математику, а если еще и не знал - совсем беда

C++

#include <iostream>
#define NOD(x, y) (a > b ? a %=b : b %= a)
using namespace std;
int main()
{
    int a, b;
    cin >> a >> b;
    while(a && b) NOD(a, b);
    cout << a+b << endl;
    return 0;
}

@NQUARE · 03.10.2020, 19:08

Сообщение от мама Стифлера

#define NOD(x, y) (a > b ? a %=b : b %= a)

Ого, прям одной строчкой

Добавлено через 1 минуту
И какой же быстрее будет работать?

C++

int Nod(int a, int b) {
    while (a && b) {
        if (a >= b) a %= b;
        else b %= a;
    }
    return a | b;
}

VS

C++

1	#define NOD(x, y) (a > b ? a %=b : b %= a)

Добавлено через 1 минуту

Сообщение от NQUARE

int Nod(int a, int b) {

Можно ещё inline сделать, если компилятор сам не сделает

Добавлено через 1 минуту

Сообщение от мама Стифлера

а если еще и не знал

Кто?)

@мама Стифлера · 03.10.2020, 19:20

Не по теме:

Сообщение от NQUARE

Кто?)

это обобщающий прикол для тех, кто совсем не знал, что то типа:
эх, не знал, да еще и забыл

@egesavran 1 / 1 / 0 Регистрация: 27.09.2020 Сообщений: 63
		1
	Вычислить наибольший общий делитель (НОД) двух натуральных чисел 03.10.2020, 00:16. Показов 6104. Ответов 6 Метки нет (Все метки) Вычислить наибольший общий делитель (НОД) натуральных чисел а, b. 0

@мама Стифлера
	03.10.2020, 19:20 Вычислить наибольший общий делитель (НОД) двух натуральных чисел #7
	Не по теме: Сообщение от NQUARE Кто?) это обобщающий прикол для тех, кто совсем не знал, что то типа: эх, не знал, да еще и забыл 0