알고리즘 기술

유클리드 호제법

헐랭미 2020. 6. 11. 11:22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#define pii pair<int, int>
using namespace std;
 
int getGCD(int a, int b)
{
    if (a < b)
        swap(a, b);
 
    int c;
    while (b)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
 
}
 
int getGCD2(int a, int b)
{
    if(b == 0)
        return a;
    else
        return getGCD2(b, a%b);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int a,b;
    cin >> a >> b;
    
     int c = getGCD(a,b); // 반복형
     int d = getGCD2(a,b); // 재귀형
}
 
cs