登录  | 立即注册

游客您好!登录后享受更多精彩

扫一扫,访问微社区

QQ登录

只需一步,快速开始

开启左侧

[寒假笔记] c语言求最大公约数

[复制链接]
发表于 2022-1-26 17:32:38 | 显示全部楼层 |阅读模式
学习笔记
学习科目: c语言
学习安排: 求最大公约数
开始时间: 2022-01-26
结束时间:
方法一:枚举:1、设t为2;
2、如果u和v都能被t整除,则记下这个t
3、t加1后重复第2步,直到t等于u和v;
4、那么,曾经记下的最大的可以同时整除u和v的t就是gcd(最大公约数)
方法二:辗转相除法:1、如果b等于0,计算结束,a就是最大公约数;
2、否则,计算a除以b的余数,让a等于b,而b等于那个余数;
3、回到第一步。
比如说令a=12,b=18,t为a%b
a    b    t
12  18  12
18  12   6
12   6    0
6     0
代码如下:
#include <stdio.h>

int main()
{
        int a,b;
        int t;
        scanf("%d %d", &a, &b);
        while ( b != 0 ) {
                t = a%b;
                a = b;
                b = t;
        }
        printf("最大公约数是%d\n",a);
       
        return 0;
}

好懒~~不想说~~~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表