หา 3 จำนวนเต็ม ≤ N ที่ LCM มากที่สุดใน C++

โจทย์: กำหนด N หา 3 จำนวนเต็ม ≤ N ที่ LCM มากที่สุด

ตัวอย่าง: N=34 → 34, 33, 31 (LCM = 34×33×31 เพราะ pairwise coprime)

Logic

1. ถ้า N คี่: N, N-1, N-2 (3 ตัวติดกัน คี่-คู่-คี่ → pairwise coprime)
2. ถ้า N คู่:
   • ถ้า gcd(N, N-3) = 1 → N, N-1, N-3
   • Else → N-1, N-2, N-3

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

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

void findMaximumLCM(int n) {
    if (n % 2 != 0) {
        cout << n << " " << (n-1) << " " << (n-2);
    } else if (__gcd(n, n-3) == 1) {
        cout << n << " " << (n-1) << " " << (n-3);
    } else {
        cout << (n-1) << " " << (n-2) << " " << (n-3);
    }
}

int main() {
    int number = 34;
    findMaximumLCM(number);
}

อินพุต

34

เอาต์พุท

34 33 31

เหตุผล

LCM มากที่สุดเมื่อตัวเลข pairwise coprime มากที่สุด การเลี่ยง common factors (โดยเฉพาะ 2) ให้ LCM ใกล้เคียงผลคูณมากที่สุด