相对质数

Question

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

Answer 1

被Jim Clay的漫不经心的评论所激励，这里是Euclid的六行代码的算法：

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

更新了以添加:我已经被this answer from 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

计算Greatest Common Denominator的众多算法之一。