求最大公约数和最小公倍数的几种方法

不念不忘少年蓝@ 2023-10-06 09:42 1阅读 0赞

**最大公约数**：

1.  常规方法
2.  辗转相除法
3.  递归法
4.  三目运算符 + 递归

**最小公倍数**：

1.  常规方法
2.  利用最大公约数求解

示例代码：

1 #include<iostream>
     2 using namespace std;
     3 
     4 //最大公约数 
     5 //（1）常规方法 
     6 void gcd1(int a, int b)
     7 {
     8     int minNum = min(a, b);    
     9     for (int i = minNum; i >= 1; i--)
    10     {
    11         if (a % i == 0 && b % i == 0)
    12         {
    13             printf("%d\n", i);
    14             break;
    15         }
    16     }
    17 }
    18 
    19 //（2）辗转相除法 
    20 void gcd2(int a, int b)
    21 {
    22     int tmp;
    23     while (true) {
    24         if (a == 0) 
    25         {
    26             printf("%d\n", b);
    27             break;
    28         }
    29         
    30         tmp = a;
    31         a = b % a;
    32         b = tmp;
    33     }    
    34 }
    35 
    36 //（3）递归法 
    37 int gcd3(int a, int b)
    38 {
    39     if (b == 0)
    40         return a;
    41     else
    42         return gcd3(b, a % b);
    43 }
    44 
    45 //（4）三目运算符 + 递归 
    46 int gcd4(int a, int b)
    47 {
    48     return (b == 0) ? a : gcd4(b, a % b);
    49 }
    50 
    51 //最小公倍数
    52 //（1）常规方法 
    53 int lcm1(int a, int b)
    54 {
    55     int maxNum = max(a , b);
    56     int pro = a * b;
    57     for(int i = maxNum; i <= pro; i++)
    58     {
    59         if( i % a == 0 && i % b == 0)
    60         {
    61             printf("%d\n", i);
    62             break;
    63         }
    64     }
    65 }
    66 
    67 //（2）利用最大公约数求解 
    68 int lcm2(int a, int b)
    69 {
    70     return a * b / gcd4(a , b); 
    71 }
    72 
    73 int main()
    74 {
    75     int a = 15, b = 12;
    76     printf("15 和 12 的最大公约数为：\n");
    77     gcd1(a, b);
    78     
    79     gcd2(a, b);
    80     
    81     int t = gcd3(a, b);
    82     printf("%d\n", t);
    83     
    84     t = gcd4(a, b);
    85     printf("%d\n", t);
    86     
    87     printf("15 和 12 的最小公倍数为：\n");
    88     lcm1(a, b);
    89     
    90     t = lcm2(a ,b);
    91     printf("%d", t);     
    92     
    93     return 0;
    94 }

运行结果：

![format_png][]

[format_png]: http://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWFnZXMyMDE1LmNuYmxvZ3MuY29tL2Jsb2cvMTExOTA5Ny8yMDE3MDcvMTExOTA5Ny0yMDE3MDcyMzE4MzgxMDc2OC0xMDM3NzY5NDI1LmpwZw?x-oss-process=image/format,png