相对总数 [英] Relatively Prime Numbers

问题描述

如何在c ++中创建一个函数，以确定两个输入的数字是否相互为素数（没有共同的因素）？
例如1,3是有效的，但是2,4不会。

How to make a function in c++ to determine if two entered numbers are relatively prime (no common factors)? For example "1, 3" would be valid, but "2, 4" wouldn't.

推荐答案

镀金到由Jim Clay的不慎评论的行动，这里是Euclid的算法在六行代码：

Galvanised into action by Jim Clay's incautious comment, here is Euclid's algorithm in six lines of code:

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

更新我被来自Omnifarious 的这个答案过度混淆， code> gcd 函数因此：

Updated to add: I have been out-obfuscated by this answer from Omnifarious, who programs the gcd function thus:

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：

So now we have a three-line version of 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);
}

这篇关于相对总数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！