判断两个数互质

大数除以小数的 余数和小数比较 如果他们互质那 大数和小数就互质
public boolean check(int m, int n)
{
return check2(m > n ? m : n, m <= n ? m : n);
}

public boolean check2(int max, int min)
{
int mo = max % min;
if (mo == 0) {
return min == 1 ? true : false;
}
else {
return check2(min, mo);
}
}

gcd(a,b)==1

求余数会比较占CPU时间，这样可以避免

#include<iostream>
using namespace std;

bool check(int a , int b)
{

if(a > b) return check(a-b , b);
else if( a < b) return check(a , b-a);
else
if(a == 1) return false;
else return true;
}

void main()
{
cout << std::boolalpha << check(300 , 8) << endl;
cout << std::boolalpha << check(301 , 8) << endl;
}

用辗转相除法求最大公约数
为1则互质

521linux写的不错 还可以稍微该该

#include <iostr