พิมพ์ตัวเลขที่เฉพาะตัวประกอบเป็น Subset ของเฉพาะตัวประกอบของ X ใน C++

ภาพรวมปัญหา

ได้รับอาร์เรย์ N ตัวและตัวเลข X ต้องพิมพ์ตัวเลขในอาร์เรย์ที่เฉพาะตัวประกอบเป็น Subset ของเฉพาะตัวประกอบของ X

ตัวอย่าง

Input: X = 30, array = {2, 3, 6, 10, 12}
Output: 2 3 6

วิธีแก้ปัญหา (GCD Division)

1. แต่ละตัวเลขในอาร์เรย์ หารซ้ำด้วย GCD(ตัวเลข, X) จน GCD = 1
2. ถ้าผลลัพธ์ = 1 → เฉพาะตัวประกอบเป็น Subset → พิมพ์

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

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

void printPrimeSet(int a[], int n, int x) {
    bool flag = false;
    for (int i = 0; i < n; i++) {
        int num = a[i];
        int g = __gcd(num, x);
        while (g != 1) {
            num /= g;
            g = __gcd(num, x);
        }
        if (num == 1) {
            flag = true;
            cout << a[i] << " ";
        }
    }
    if (!flag) cout << "There are no such numbers";
}

int main() {
    int x = 60;
    int a[] = { 2, 5, 10, 7, 17 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Numbers whose set of prime numbers is subset of set of prime factor of " << x << "\n";
    printPrimeSet(a, n, x);
    return 0;
}

ผลลัพธ์ (Output)

Numbers whose set of prime numbers is a subset of the set of prime factor of 60
2 5 10