Относительно простые числа

Question

Как сделать функцию в c ++, чтобы определить, являются ли два введенных числа относительно простыми (нет общих факторов)? Например, «1, 3» будет допустимым, а «2, 4» - нет.

Answer 1

Гальванизировано в действие неосторожным комментарием Джима Клэя, вот алгоритм Евклида в шести строках кода:

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

Обновлен , чтобы добавить: я был затенен это ответ от 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

Один из многих алгоритмов для вычисления Величайшего общего знаменателя .