หา Non-Transitive Coprime Triplet ใน Range ใน C++

สมมติมี Lower และ Upper Bound ต้องการหา Non-Transitive Triplet (x, y, z) ที่ (x, y) เป็น Coprime (GCD=1), (y, z) เป็น Coprime แต่ (x, z) ไม่ใช่ Coprime ตัวอย่าง Lower=2, Upper=10 Elements {2,3,4,5,6,7,8,9,10} Triplet ที่เป็นไปได้คือ (4, 7, 8) เพราะ (4,7) และ (7,8) เป็น Coprime แต่ (4,8) ไม่ใช่

ใช้ Naive Approach: Generate Triplets ทั้งหมดใน Range แล้วตรวจสอบเงื่อนไข

ตัวอย่างโค้ด C++

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