In Tất Cả Số Có Tập Thừa Số Nguyên Tố Là Tập Con Của Thừa Số Nguyên Tố Của X Trong C++

Trong bài toán này, chúng ta được cho một tập N số và một số X. In tất cả số từ mảng mà tập thừa số nguyên tố của nó là tập con của tập thừa số nguyên tố của X.

Ví dụ để hiểu vấn đề:

Đầu vào: X = 30, mảng = {2, 3, 6, 10, 12} → Đầu ra: 2 3 6

Để giải quyết, ta duyệt các phần tử mảng. Chia phần tử cho gcd của (phần tử, X). Lặp chia cho đến khi gcd = 1. In số còn lại.

Ví Dụ

#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 << "Không có số nào thỏa mãn";
}

int main() {
    int x = 60;
    int a[] = { 2, 5, 10, 7, 17 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Số có tập thừa số nguyên tố là tập con của thừa số nguyên tố của " << x << ":\n";
    printPrimeSet(a, n, x);
    return 0;
}

Đầu Ra

Số có tập thừa số nguyên tố là tập con của tập thừa số nguyên tố của 60

2 5 10