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.

FishBasketGordo
  • 22,904
  • 4
  • 58
  • 91
Cobold
  • 2,563
  • 6
  • 34
  • 51

2 Answers2

10

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 ;
  }
}

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));
}

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);
}
Community
  • 1
  • 1
TonyK
  • 16,761
  • 4
  • 37
  • 72
  • 5
    +1 for the "horrible" code style; I got goosebumps reading it. – hardmath Jun 23 '11 at 12:54
  • 1
    +1 for horrible code style - it honors Euclid. Any simple, clear explanation of how it works is missing the pure genius of the astonishing theorem. – DaveWalley Aug 14 '14 at 20:31
5

One of the many algorithms for computing the Greatest Common Denominator.

mikerobi
  • 20,527
  • 5
  • 46
  • 42
  • As referenced in that Wikipedia article under "Further Reading", Knuth's AOCP v.2 (Seminumerical Algorithms) has good analysis of the efficiency of several approaches. – hardmath Jun 23 '11 at 13:01