给定两个整数,让你求这两个数的最大公约数
最大公约数顾名思义就是:这几个整数共有的约数中最大的一个。
目录
1. 辗转相除法
思路:
(1)将两个整数求余数a%b = c;如果c = 0,则b为最大公约数
(2)如果c != 0,则让a = b, b = c,继续执行a%b = c;判断条件为c是否为零
例如:a = 15,b = 18
c = a%b = 15%18 = 15,c = 15,c此时不等于0;
则进行a = b,b = c;a = 18,b = 15;
继续执行c = a%b = 18%15 = 3,此时c=3不为0;
执行a = b, b = c;a = 15,b = 3;
继续进行c = a%b = 15%3 = 0;此时c = 0循环结束。
代码如下:
#include<stdio.h>
int main()
{
int a, b, c;
printf("请输入两个整数:");
scanf("%d%d", &a, &b);
c = a % b;
while (c != 0)
{
a = b;
b = c;
c = a % b;
}
printf("最大公约数为:%d", b);
return 0;
}
2.更相减损法
思路:
(1)如果a = b;则a或b就是最大公约数
(2)如果a != b;若a>b,则a = a-b;若a<b,则b = b-a;一直执行到a = b循环结束
例如:a = 15,b = 18
因为a != b且a<b,则b = a-b = 18-15 = 3,
b = 3,a>b,则a = a-b = 15-3 = 12 ,
a = 12,a>b,则a = a-b =12-3 = 9,
a = 9,a>b,则a = a-b =9-3 = 6,
a = 6,a>b,则a = a-b =6-3 = 3,
a = 3,a = b = 3,此时a = b = 3循环结束。
代码如下:
#include <stdio.h>
int main()
{
int a, b;
printf("请输入两个整数:");
scanf("%d %d", &a, &b);
while (a != b)
{
if (a > b)
a = a - b;
else
b = b - a;
}
printf("最大公约数为:%d\n", a);
return 0;
}
3.穷举法
思路:
(1)选出a和b最小的数放入c中,然后分别用a和b对c求余数,看是否能被c整除,同时能被c整除则c是这两个数的最大公约数
(2)如果不能被c同时整除,c进行减一(c--),一直执行到a和b同时能被c整除。
例如:a = 15,b = 18
把较小值赋给c,c = 15,a%c = 15%15 = 0,b = b%c = 18%15 = 3,不能同时被c整除,循环继续 c--;
a%c = 15%14 = 1,b = b%c = 18%14 = 4,不能同时被c整除,循环继续 c--;
....(不一一列举了)
a%c = 15%3 = 0,b = b%c = 18%3 = 0,能同时被c整除,循环结束。
代码如下:
#include<stdio.h>
int main()
{
int a, b;
int c = 0;
printf("请输入两个整数:");
scanf("%d %d", &a, &b);
c = (a > b) ? b : a; //三目运算符 将最小的赋给c
while (a % c != 0 || b % c != 0)
{
c--;
}
printf("最大公约数为:%d\n", c);
}
最后,文章结束啦!!