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)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!