โปรแกรม C++ ตรวจสอบว่าจำนวนเต็มเป็นคู่เฉพาะสัมพัทธ์ (Coprime) หรือไม่

กำหนดอาร์เรย์ nums ขนาด n ต้องจัดประเภทว่า:

• Pairwise Coprime: gcd(nums[i], nums[j]) = 1 สำหรับทุกคู่ i < j
• Setwise Coprime: gcd(nums[0], nums[1], ..., nums[n-1]) = 1 (แต่ไม่ใช่ pairwise)
• Not Coprime: gcd ของทั้งชุด > 1

ตัวอย่าง: n=4, nums={7,11,13,17} ผลลัพธ์: The numbers are pairwise coprime

ขั้นตอนการแก้ปัญหา

1. คำนวณ gcdVal = GCD ของทั้งอาร์เรย์ พร้อมนับความถี่ fac[x]
2. ถ้า gcdVal != 1 → Not Coprime
3. ถ้า gcdVal == 1 ตรวจสอบ pairwise:
   • ใช้ Sieve แบบง่าย: สำหรับจำนวนเฉพาะ k นับจำนวนตัวในอาร์เรย์ที่หารด้วย k ลงตัว (c)
   • ถ้ามี k ใดที่ c > 1 → ไม่ใช่ pairwise
4. ถ้า pairwise จริง → Pairwise Coprime มิฉะนั้น → Setwise Coprime

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

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

void solve(int n, int nums[]) {
    int fac[100] = {0};
    bool checkPrime[100] = {0};
    int gcdVal = 0;
    for (int i = 0; i < n; i++) {
        gcdVal = __gcd(nums[i], gcdVal);
        ++fac[nums[i]];
    }
    if (gcdVal == 1) {
        bool pw = true;
        for (int k = 2; k < 100; ++k) {
            if (checkPrime[k]) continue;
            int c = 0;
            for (int j = k; j < 100; j += k) {
                c += fac[j];
                checkPrime[j] = true;
            }
            pw = pw && c <= 1;
        }
        if (pw) cout << "The numbers are pairwise coprime";
        else cout << "The numbers are setwise coprime";
    } else {
        cout << "The numbers are not coprime";
    }
}

int main() {
    int n = 4, nums[] = {7, 11, 13, 17};
    solve(n, nums);
    return 0;
}

อินพุต / เอาต์พุต

Input: 4, {7, 11, 13, 17}

Output: The numbers are pairwise coprime