Tìm 3 số ≤ N có LCM lớn nhất trong C++

Cho N, tìm 3 số ≤ N sao cho LCM (bội chung nhỏ nhất) của chúng lớn nhất.

Quan sát

• N lẻ: chọn N, N-1, N-2 (3 số liên tiếp, 2 số lẻ → LCM = tích).
• N chẵn:
  • Nếu gcd(N, N-3) == 1: chọn N, N-1, N-3.
  • Ngược lại: chọn N-1, N-2, N-3.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

void maxLCMTriplet(int n) {
    if (n % 2 == 1) {
        cout << n << " " << n-1 << " " << n-2;
    } else if (std::gcd(n, n-3) == 1) {
        cout << n << " " << n-1 << " " << n-3;
    } else {
        cout << n-1 << " " << n-2 << " " << n-3;
    }
}

int main() {
    maxLCMTriplet(34); // 34 33 31
    return 0;
}

Kết quả

34 33 31

Giải thích: Tránh chọn 3 số chẵn (LCM nhỏ). Ưu tiên các số nguyên tố cùng nhau.