求两个数最大公因数的c语言程序

　

最大公因数

对于这个问题,我能想到的方法有三种:

①先找出这两个数中最小的那个,可以用i表示,然后用这两个数依次对i取余. 同时i不断减1,直到这两个数对i取余都为0;这时的i就为最大公因数

程序如下:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int main(){
	int a = 0;
	int b = 0;
	int i = 0;
	printf("输入 a b:");
	scanf("%d%d", &a, &b);
	if (a > b){
		i = b;
	}
	else i = a;
	while (a%i != 0 || b%i != 0){
		i--;
	}
	printf("最大公因数为%d\n", i);
	system("pause");
	return 0;
}

②辗转相除法:用其中一个数除以另外那个数,再用除数除以得到的余数,重复这个过程,直到余数为0.余数为0的等式中那个除数就是最大公因数.

程序如下:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int main(){
	int a = 0;
	int b = 0;
	int i = 1;
	printf("输入 a b:");
	scanf("%d%d", &a, &b);
	if (a == b){
		printf("最大公因数为%d\n", a);
	}
	else {
		while (i != 0){
			i = a%b;
			a = b;
			b = i;
		}
		printf("最大公因数为%d\n", a);
	}
	system("pause");
	return 0;
}

③更相减损术:用较大的那个数减去较小的那个数,再用减数和差中,较大的那个减去较小的那个,重复这个过程,直到减数和差相等.减数就为最大公因数.

程序如下:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
int main(){
	int a = 0;
	int b = 0;
	int i = 1;
	printf("输入 a b:");
	scanf("%d%d", &a, &b);
	if (a == b){
		printf("最大公因数为%d\n", a);
	}
	else {
		while (a != b){
			if (a > b)  a = a - b;
			if (a < b)  b = b - a;
		}
		printf("最大公因数为%d\n", a);
	}
	system("pause");
	return 0;
}

以上就是这三种方法的程序代码,当然我目前只知道这三种方法,其他方法还不是很了解.

相关阅读

最大公因数

#include<stdio.h> int main() { int number, x, y, num1, num2, sum, count=1; scanf("%d\n", &number); scanf("%d %d\n",