相对素数

Question

如何在c ++中创建一个函数来确定两个输入的数字是否相对为素数(没有公因子)？例如,"1,3"将是有效的,但"2,4"不会.

Answer 1

吉姆·克莱(Jim Clay)的不谨慎评论激励他们采取行动,以下是欧几里德的六行代码算法:

bool RelativelyPrime (int a, int b) { // Assumes a, b > 0
  for ( ; ; ) {
    if (!(a %= b)) return b == 1 ;
    if (!(b %= a)) return a == 1 ;
  }
}

更新以添加:我已经被Omnifarious的这个答案混淆了,Omnifarious负责编程这个gcd函数:

constexpr unsigned int gcd(unsigned int const a, unsigned int const b)
{
   return (a < b) ? gcd(b, a) : ((a % b == 0) ? b : gcd(b, a % b));
}

所以现在我们有了一个三线版的RelativelyPrime:

bool RelativelyPrime (int a, int b) { // Assumes a, b > 0
   return (a<b) ? RelativelyPrime(b,a) : !(a%b) ? (b==1) : RelativelyPrime (b, a%b);
}

Answer 2

计算最大公分母的众多算法之一.