最大公约数

循环法

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
#include<iostream>

using namespace std;

int gcd1(int x,int y){
    if(x%y==0){
        return y;
    }
    return gcd1(y,x%y);
}

int gcd2(int x,int y){
    int r = x % y;
    while( r )
    {
        x = y;
        y = r;
        r = x % y;
    }
    return y;

}

int lcm(int x,int y){
    int k = gcd2(x,y);
    return x*y/k;
}
int main(){
    int x=60,y=95;
    cout<<gcd1(x,y);
    return 0;
}

递归法

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
#include<iostream>

using namespace std;

int gcd1(int x,int y){
    if(x%y==0){
        return y;
    }
    return gcd1(y,x%y);
}

int gcd2(int x,int y){
    int r = x % y;
    while( r )
    {
        x = y;
        y = r;
        r = x % y;
    }
    return y;

}

int lcm(int x,int y){
    int k = gcd2(x,y);
    return x*y/k;
}
int main(){
    int x=60,y=95;
    cout<<gcd1(x,y);
    return 0;
}

最小公倍数

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
#include<iostream>

using namespace std;

int gcd1(int x,int y){
    if(x%y==0){
        return y;
    }
    return gcd1(y,x%y);
}

int gcd2(int x,int y){
    int r = x % y;
    while( r )
    {
        x = y;
        y = r;
        r = x % y;
    }
    return y;

}

int lcm(int x,int y){
    int k = gcd2(x,y);
    return x*y/k;
}
int main(){
    int x=60,y=95;
    cout<<gcd1(x,y);
    return 0;
}