如何求两个数最大公约数

63 阅读 0 评论 42 点赞

我是靠谱客的博主任性小天鹅，最近开发中收集的这篇文章主要介绍如何求两个数最大公约数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、程序描述
求两个数最大公约数，可以用四种方法，分别是暴力穷举法（不适用于大数字）、辗转相除法（线性代数）、更相减损法（九章算术）、stein算法（Stein算法跟更相减损术很像，而且只有比较、移位、减法，非常适合用FPGA实现。）
二、程序要点
1、暴力穷举法，由于是求最大公约数，所以从大到小求较为适用。利用system（）函数清楚屏幕。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
int main() 
{
	int a = 0;
	int b = 0;
	printf("请输入两个整数:");
	scanf_s("%d%d", &a, &b);
	//vs更安全的函数
	if (a >= b) 
	//谁小穷举到谁为止，从大到小试
	{
		int i = 0;
		for (i = b; i >= 1; i--) 
		{
			if (a % i == 0 && b % i == 0) 
			{
				system("cls");
				printf("这两个数的最大公约数为：%dn", i);
				break;
			}
		}
	}
	else 
	{
		int j = 0;
		for (j = a; j >= 1; j--) 
		//谁小穷举到谁，从大到小试
		{
			if (a % j == 0 && b % j == 0) 
			{
				system("cls");
				printf("这两个数最大公约数为：%dn", j);
				break;
			}
		}
	}
	system("pause");
	return 0;
}

2、辗转相除法
线性代数方法，用大数对小数求余，若余数为0，则除数为最大公约数。若余数不为0，将此余数作为除数，小数作为被除数，重新求余，直到余数为0为止。此时的最大公约数为余数。这个方法比暴力穷举法效率高很多。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
int main() 
{
	int a = 0;
	int b = 0;
	printf("请输入两个整数:");
	scanf_s("%d%d", &a, &b);
	if (a >= b) 
	{
		int c = a % b;
		while (c != 0) 
		{
			a = b;
			b = c;
			c = a % b;
		}
		system("cls");
		printf("最大公约数为：%dn", b);//辗转相除法余数为0前一个数，余数和这个数辗转相处
	}
	else 
	{
		int d = b % a;
		while (d != 0) 
		{
			b = a;
			a = d;
			d = b % a;
		}
		system("cls");
		printf("最大公约数为：%dn", a);//辗转相除法余数为0前一个数，余数和这个数辗转相处
	}
	system("pause");
	return 0;
}

3、更相减损法
两个数如果相等，那么公约数为他们中的一个，当两个数不相等时，用大数减小数得到的差和之前的那个较小的数再次相减，直到两个数相等，得到最大公约数。这个程序的代码量较少。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<stdlib.h>
int main() 
{
	int a = 0;
	int b = 0;
	printf("请输入两个整数:");
	scanf_s("%d%d", &a, &b);//vs更安全
	while ((a - b) != 0) 
	{
		if (a > b) 
		{
			a = a - b;
		}
		else 
		{
			b = b - a;
		}
	}
	system("cls");
	printf("最大公约数为：%dn", b);
	system("pause");
	return 0;
}

4、stein算法
在上述2、3两种方法的基础上进行更多的优化，有了stein算法，只有比较、移位、减法或者求余，更加的便捷。
用到了几个概念，惰性运算，移位等于除以二，和1求&的关系

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main()
{
	int a = 0;
	int b = 0;
	printf("请输入两个整数:");
	scanf_s("%d%d", &a, &b);
	int gcd = 0;//gcd最大公约数
	int k = 1;
	while ((!(a & 1)) && (!(b & 1)))//&&是惰性运算，当前面为假的时候就不执行后面了，||也是惰性运算，如果前面为真就不执行后面了。
	{
		k <<= 1;//用k记录全部公因子2的乘积 乘以2；
		a >>= 1;//2进制位移一个单位就是除以2
		b >>= 1;
	}
	while (!(a & 1))//偶数和1&得到的是0，奇数是1
		a >>= 1;
	while (!(b & 1))
		b >>= 1;
	if (a < b)
	{
		a ^= b, b ^= a, a ^= b;//交换，使a为较大数； 
	}
	while (a != b)
	{
		a -= b;
		if (a < b)
		{
			a ^= b, b ^= a, a ^= b;//交换
		}	
	}
	gcd = k * a;
	system("cls");
	printf("最大公约数为：%dn", gcd);
	system("pause");
	return 0;
}