Trong bài toán này, chúng ta được cho một số nguyên n và chúng ta phải in ra tất cả các số nguyên tố nhân nhỏ hơn hoặc bằng n.
Số nguyên tố nhân đôi là các số nguyên tố mà tích các chữ số của chúng cũng là số nguyên tố. Như 2, 3, 5, 7, 13, 17.
23 là số nguyên tố nhưng không phải là số nguyên tố nhân vì 2 * 3 =6.
Hãy lấy một ví dụ để hiểu vấn đề -
Input: n = 9 Output: 2 3 5 7
Để giải quyết vấn đề này, chúng ta sẽ tìm tất cả các số nguyên tố nhỏ hơn n. Và kiểm tra xem số có phải là số nguyên tố nhân không . Và in tất cả các số nguyên tố nhân nhỏ hơn n.
Ví dụ
Chương trình minh họa giải pháp cho vấn đề
#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<<"All multiplicative Prime Numbers =< "<<n<<" are :\n";
generateMprime(n);
} Đầu ra
All multiplicative Prime Numbers =< 10 are − 2 3 5 7