C++の範囲で非推移的な互いに素なトリプレットを見つける

下限と上限があり、ペア（x、y）が互いに素（GCDは1）、ペア（y、z）が互いに素であるような非遷移トリプレット（x、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;
   // Generate and check for all possible triplets
   // between L and 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