C/C++教程

C++: 判断两个数互质（最大公约数为1)

本文主要是介绍C++: 判断两个数互质（最大公约数为1)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

**定理：gcd(a,b) = gcd(b,a mod b) ** // a和b的最大公因数，a和b的大小没影响。

①0和任意自然数的最大公约数就是那个自然数。

②互质指最大公约数等于1的两个自然数。

③1和任意数互质。

判断是否互质代码如下：（如果求最大公因数，输出b即可）

bool isrp(int a, int b){
	if(a==1||b==1)     // 两个正整数中，只有其中一个数值为1，两个正整数为互质数
		return true;
	while(1){          // 求出两个正整数的最大公约数
		int t = a%b;
		if(t == 0) break;
		else{
			a = b;
			b = t;
		}
	}
	if(b>1)	return false;// 如果最大公约数大于1，表示两个正整数不互质
	else return true;	// 如果最大公约数等于1,表示两个正整数互质

【C++笔记】 判断两个数互质（做大公约数为1）

这篇关于C++: 判断两个数互质（最大公约数为1)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航