Tìm bộ ba coprime không bắc cầu trong khoảng cho trước trong C++

Cho khoảng [left, right]. Tìm bộ ba (x, y, z) sao cho (x,y) và (y,z) là cặp coprime (UCLN=1) nhưng (x,z) KHÔNG coprime. Ví dụ left=2, right=10 → bộ ba (4,7,8) hoặc (8,9,10).

Cách làm: sinh tất cả bộ ba có thể trong khoảng, kiểm tra điều kiện UCLN.

Ví dụ

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

Kết quả

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