求最大公约数和最小公倍数（之和）—— C语言

柔光的暖阳◎ 2023-09-29 10:38 10阅读 0赞

**目录**

1. 求最大公约数

1.1第一种方法 暴力求解

1.2 第二种方法 辗转相除法

1.3 第三种方法 相减法

2.求最小公倍数

2.1 第一种方法 暴力求解

2.2 第二种方法 在最大公约数的基础上求

3.看一个牛客网上的练习题

--------------------

## 1. 求最大公约数 ##

### 1.1第一种方法 暴力求解 ###

这种方法是最容易想到的，下面看一下思路，比如说找16 18 最大公约数

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_7_color_FFFFFF_t_70_g_se_x_16][]![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_11_color_FFFFFF_t_70_g_se_x_16][]

取到两个数，先判断大小，将小的拿出来。然后用小的这两个数进行取模运算。如果不是对这个取出来的数“--”

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_12_color_FFFFFF_t_70_g_se_x_16][]

### 1.2 第二种方法 辗转相除法 ###

这种方法也是最不容易想到的，但却是比暴力求解更有效率的一种方法，下面看一下原理

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_7_color_FFFFFF_t_70_g_se_x_16 1][]![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_14_color_FFFFFF_t_70_g_se_x_16][]

不用对两个数判断大小，直接取模，如果不为零执行while中的语句，将m赋值给n，然后将取模后的数字，赋值给m，这样循环下来，当模为零时跳出来 ，max就是最大公约数

### 1.3 第三种方法 相减法 ###

最大公约数还有这样一种性质

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_20_color_FFFFFF_t_70_g_se_x_16][]

所以我们可以根据这个性质来 ，求最大公约数

#include <stdio.h>
    
    int main()
    {
        int a = 0;
        int b = 0;
        scanf("%d%d",&a,&b);
        while(a!=b)
        {
            if(a>b)
            a = a - b;
            if(a<b)
            b = b - a;
        }
        printf("%d\n",a);
        return 0;
    }

## 2.求最小公倍数 ##

### 2.1 第一种方法 暴力求解 ###

和前面的求最大公约数方法基本一样

![34984025161641b282aa8a30127949e1.png][]![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_9_color_FFFFFF_t_70_g_se_x_16][]

### 2.2 第二种方法 在最大公约数的基础上求 ###

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_14_color_FFFFFF_t_70_g_se_x_16 1][]

## 3.看一个牛客网上的练习题 ##

链接 [小乐乐与欧几里得\_牛客题霸\_牛客网 (nowcoder.com)][_nowcoder.com]

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_19_color_FFFFFF_t_70_g_se_x_16][]

我们直接用辗转相除法来做

int main()
     {
         long long n, m;
         long long max = 0, min = 0, tmp = 0;
         scanf("%lld %lld\n", &n, &m);
         //最大公约数
         long long a = n, b = m;
         while (tmp = n % m)
         {
             n = m;
             m = tmp;
         }
         max = m;
         //最小公倍数
         min = a * b / max;
         printf("%lld\n", min + max);
         return 0;
     }

--------------------

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_7_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/51536e4cf15049fbb8ec3a5604f3f85f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA,size_7,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_11_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/7294b4fa851b43b1967293282212a5ff.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_12_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f2d3dfdca8bc4076a82c0d6ed851643a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA,size_12,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_7_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/8d90131af2e2484f9719a7ffb128da1e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA,size_7,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_14_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/5d623dc8ade8476ab21f09c1dc930e15.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA,size_14,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/3db62c576e464162ad2331d3595246ab.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA,size_20,color_FFFFFF,t_70,g_se,x_16
[34984025161641b282aa8a30127949e1.png]: https://img-blog.csdnimg.cn/34984025161641b282aa8a30127949e1.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_9_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/93eb254807cc4e40b0966f9a002dcd84.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA,size_9,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_14_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/206171d1b7eb41fd986cd303acdaaa79.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA,size_14,color_FFFFFF,t_70,g_se,x_16
[_nowcoder.com]: https://www.nowcoder.com/practice/da13e0cf321e4df9acd0fdf0a433cbb0?tpId=290&tqId=632016&ru=/exam/oj&qru=/ta/beginner-programmers/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E8%25AF%25AD%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D290
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA_size_19_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/de07b9834c53429f967eb2a36803a660.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5b-r5Yiw6ZSF6YeM5p2l5ZGA,size_19,color_FFFFFF,t_70,g_se,x_16