#include<stdio.h>
int main() {
int a, b, t;
printf("请输入两个数!\n");
scanf("%d%d",&a,&b);
if (a == b) {
printf("最大公约数%d\n", a);
}
else {
while (a != b) {
if (a > b)
a = a - b;
else
b = b - a;
}
printf("最大公约数是:%d\n", a);
}
return 0;
}
int gcd(int a, int b);
int main(void)
{
int num1,num2;
puts("请输入两个数");
scanf("%d%d", &num1, &num2);
// 不需要判断num1和num2的大小,因为gcd(a, b) == gcd(b, a)
printf("最大公约数为%d", gcd(num1,num2));
return 0;
}
int gcd(int a, int b)//辗转相除法 欧几里德算法(大除以小)
{
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a; // 当b为0时,a就是最大公约数
}
//在欧几里得算法中,我们重复地将较大的数替换为两数相除的余数,同时保持另一个数不变。这个过程一直进行,直到余数为
0
。此时,非零的那个数就是两个原始数的最大公约数(GCD)。
2.辗转相减法
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int Dect(int a, int b);//更相减损法 被减数减去减数 直到差和减数相等即为最大公约数
int main(void)
{
int num1,num2;
puts("请输入两个整数");
scanf("%d%d", &num1, &num2);
/*
while (((num1 % 2) == 0) && ((num2 % 2) == 0)) {
num1 /= 2;
num2 /= 2;
}
最后还要乘回去看看除了几次2
*/
if (num1 > num2) {
printf("最大公约数为%d", Dect(num1, num2));
}
else {
printf("最大公约数为%d", Dect(num2, num1));
}
return 0;
}
int Dect(int a, int b)
{
while ((a-b) !=b) {//判断那个更大 差和被减数未知(大减小)
a = a-b>b?a-b:b;
b = a - b < b ? a - b : b;
}
//精妙写法
//// 循环直到a和b相等
//while (a != b) {
// // 如果a大于b,则从a中减去b
// if (a > b) {
// a -= b;
// }
// // 否则(即a小于或等于b),从b中减去a(虽然当a=b时这一步是多余的,但不影响结果)
// else {
// b -= a;
// }
//}
#include <cstdio>
using namespace std;
/*
* 辗转相除法求最大公约数
*/
int max_common_divisor(int m, int n) {
int res, a = m, b = n;
if (n > m) a = n, b = m;
for (; b != 0; b = a % b) {
res = b;
}
return res;
}
int main() {
printf("%d", max_common_divisor(12, 16));
return 0;
}
//输入两个正整数 m 和 n,求其最大公约数(辗转相除法)
int com_divisor(int m, int n) {
int mod;
while (mod = m % n) {
m = n;
n = mod;
}
return n;
}
int main(void)
{
int m, n, d;
printf("Please Input two numbers so that get their greatest common divisor and least common multiple: ");
scanf("%d%d", &m, &n);
d = com_divisor(m, n);
printf("The greatest common divisor of %d and %d is %d, least common multiple is %d!\n", m, n, d, m * n / d);
return 0;
}
#include <stdio.h>
//辗转相除法
int main(){
int m,n,max,min,tep;
scanf("%d %d",&m,&n);
max = m;min = n;
while (max % min != 0) {
if(max < min){
int temp;
temp = max;
max = min;
min = temp;
}
tep = max % min;
max = min;
min = tep;
}
printf("%d %d 的最大公约数是:%d",m,n,tep);
return 0;
}
#include<stdio.h>
int main()
{
int m,n;
scanf("%d %d",&m,&n);
int max = 0;
for(int i = 1;i < m / 2 && i < n / 2;i++)
{
if(m % i == 0 && n % i == 0 && i > max)
{
max = i;
}
}
printf("%d\n",max);
return 0;
}
#include<stdio.h>
int main()
{
int m, n, k = 1;
static int a[10];
scanf("%d%d", &m, &n);
for(int i = 0; i < m || i < n; i++)
{
if((m % k == 0) && (n % k == 0))
a[i] = k;
k++;
}
int j = 0;
for(int i = 1; i < 10; ++i)
{
if(a[j] < a[i])
{
if(a[i] != 0)
j = i;
}
}
printf("%d和%d的最大公约数为:%d", m, n, a[j]);
return 0;
}
int main()
{
int m, n, i;
printf("输入两个整数:\n");
scanf("%d%d", &m, &n);
i = m < n ? m:n;
while (m % i != 0 || n % i != 0)
i--;
printf("i=%d是%d和%d的最大公约数", i, m, n);
return i;
}
#include <stdio.h>
int main(){
int m,n;
do {
printf_s("请输入正整数m:");
scanf_s("%d",&m);
printf_s("请输入正整数n:");
scanf_s("%d",&n);
} while (m<=0||n<=0);
if(m<n){
int temp =m;
m=n;
n=temp;
}
while (m%n!=0){
int temp=m%n;
m=n;
n=temp;
}
printf_s("最大公约数为:%d",n);
return 0;
};
#include <stdio.h>
#define N 10
int GreatestCommonFraction(int m,int n);
int main(){
int x,y,gcf,i=0;
while(i<10){
printf("%d\n",i+1);
printf("x:");
scanf("%d",&x);
printf("y:");
scanf("%d",&y);
gcf=GreatestCommonFraction(x,y);
printf("greatest common fraction of x and y:%d",gcf);
i++;
printf("\n");
}
return 0;
}
int GreatestCommonFraction(int m,int n){
if(m>=n){
int r=m%n;
while(r!=0){
m=n;
n=r;
r=m%n;
}
return n;
}else{
int r=n%m;
while(r!=0){
n=m;
m=r;
r=n%m;
}
return m;
}
}
#include<stdio.h>
#include<math.h>
int gcd(int a, int b){
int r;
while(b){
r = a % b;
a = b;
b = r;
}
return a;
}
int main(){
printf("%d",gcd(2,4));
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
#include<stdio.h>
int main()
{
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
int m = a>b?a:b;
while (1)
{
if (m % a == 0 & m % b == 0)
{
printf("%d\n", m);
break;
}
m++;
}
int main() {
int x, y, z;
int i = 1;
scanf("%d%d", &x, &y);
if (x > y) {
for (i = 1; i < x; i++) {
if (x % i == 0 && y % i == 0) {
z = i;
}
}
}
if (x < y) {
for (i = 1; i < y; i++) {
if (x % i == 0 && y % i == 0) {
z = i;
}
}
}
printf("%d\n", z);
return 0;
}
int main() {
int x, y, z;
int i = 1;
scanf("%d%d", &x, &y);
if (x > y) {
for (i = 1; i < x; i++) {
if (x % i == 0 && y % i == 0) {
z = i;
}
}
}
if (x < y) {
for (i = 1; i < y; i++) {
if (x % i == 0 && y % i == 0) {
z = i;
}
}
}
printf("%d\n", z);
return 0;
}
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include <malloc.h>
int main() {
int m, n, i;
scanf("%d %d", &m, &n);
if (m > n)
i = n;
else i = m;
while (!(m % i == 0 && n % i == 0)) {
i--;
}
printf("%d", i);
return 0;
}
#include <stdio.h>
int main(){
int a; // 除数
int b; // 被除数
int r=1; // 余数,赋初值为1
scanf("%d%d",&a,&b);
while(r!=0){ // 如果a<b,亦无需颠倒ab,在计算中商0余除数本身,在下次运算中自可颠倒回来
r = a % b;
a = b;
b = r;
}
printf("最大公约数为:%d\n",a); // 此时b的值已经在a中了,所以输出的a就是最大公约数
return 0;
}
登录后提交答案