In Tất Cả Số Nguyên Tố Nhân (Multiplicative Primes) ≤ N Trong C++

Trong bài toán này, chúng ta được cho một số nguyên n và phải in tất cả các số nguyên tố nhân (multiplicative primes) nhỏ hơn hoặc bằng n.

Số nguyên tố nhân là số nguyên tố mà tích các chữ số của nó cũng là số nguyên tố. Ví dụ: 2, 3, 5, 7, 13, 17.

23 là số nguyên tố nhưng không phải số nguyên tố nhân vì 2*3 = 6.

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

Đầu vào: n = 9 → Đầu ra: 2 3 5 7

Để giải quyết, ta tìm tất cả số nguyên tố < n. Kiểm tra xem số đó có phải số nguyên tố nhân. In tất cả số nguyên tố nhân <= n.

Ví Dụ

Chương trình minh họa giải pháp:

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

int digitMultiply(int n) {
    int prod = 1;
    while (n) {
        prod = prod * (n % 10);
        n = n / 10;
    }
    return prod;
}

void generateMprime(int n) {
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
    prime[0] = prime[1] = false;
    for (int p = 2; p * p <= n; p++) {
        if (prime[p]) {
            for (int i = p * 2; i <= n; i += p)
                prime[i] = false;
        }
    }
    for (int i = 2; i <= n; i++) {
        if (prime[i] && prime[digitMultiply(i)])
            cout << i << "\t";
    }
}

int main() {
    int n = 10;
    cout << "Tất cả số nguyên tố nhân ≤ " << n << " là:\n";
    generateMprime(n);
    return 0;
}

Đầu Ra

Tất cả số nguyên tố nhân ≤ 10 là: 2 3 5 7