在C ++中找到某个范围内的非传递性互质三元组

假设我们有下限和上限，并且我们必须找到非传递性三元组(x,y,z)，使得对(x,y)是互质的（GCD为1），对(y,z)是互质的，但对(x,z)不是互质对。例如，如果下限是2，上限是10，则元素是{2，3，4，5，6，7，8，9，10}，这里可能的三元组是（4，7，8 ），此处(4,7)和(7,8)是互质的，但(4,8)不是互质的。

我们将采用幼稚的方法来解决此问题。我们将生成下限和上限范围内的所有可能的三元组，然后匹配条件。

示例

#include <iostream>
#include <algorithm>
using namespace std;
bool isCoprime(int a, int b){
   return (__gcd(a, b) == 1);
}
void tripletInRange(int left, int right) {
   bool flag = false;
   int A, B, C;
   //生成并检查所有可能的三元组
   //在L和R之间
   for (int a = left; a <= right; a++) {
      for (int b = a + 1; b <= right; b++) {
         for (int c = b + 1; c <= right; c++) {
            if (isCoprime(a, b) && isCoprime(b, c) && ! isCoprime(a, c)) {
               flag = true;
               A = a;
               B = b;
               C = c;
               break;
            }
         }
      }
   }
   if (flag == true) {
      cout << "(" << A << ", " << B << ", " << C << ")" << " is one
      such possible triplet between " << left << " and " << right << endl;
   } else {
      cout << "No Such Triplet exists between " << left << " and " << right << endl;
   }
}
int main() {
   int left = 2, right = 10;
   tripletInRange(left, right);
}

输出结果

(8, 9, 10) is one such possible triplet between 2 and 10