Cho số nguyên N, in tất cả số bán nguyên tố ≤ N.
Số bán nguyên tố là số bằng tích của hai số nguyên tố phân biệt.
Ví dụ: 21 = 3*7 là bán nguyên tố. 25 = 5*5 không phải vì hai thừa số trùng nhau.
Ví dụ:
Input: N = 15 Output: 6 10 14 15
Giải pháp: Kiểm tra từng số ≤ N có đúng 2 thừa số nguyên tố phân biệt hay không.
Mẹo: Bắt đầu từ 6 vì 6 là số bán nguyên tố nhỏ nhất.
Chương trình minh họa
#include <bits/stdc++.h>
using namespace std;
vector<int> generateSemiPrimeNumbers(int n){
int index[n + 1];
for (int i = 1; i <= n; i++)
index[i] = i;
int countDivision[n + 1];
for (int i = 0; i < n + 1; i++)
countDivision[i] = 2;
for (int i = 2; i <= n; i++) {
if (index[i] == i && countDivision[i] == 2) {
for (int j = 2 * i; j <= n; j += i) {
if (countDivision[j] > 0) {
index[j] = index[j] / i;
countDivision[j]--;
}
}
}
}
vector<int> semiPrime;
for (int i = 2; i <= n; i++) {
if (index[i] == 1 && countDivision[i] == 0)
semiPrime.push_back(i);
}
return semiPrime;
}
int main(){
int n = 15;
cout << "Các số bán nguyên tố ≤ " << n << " là :\n";
vector<int> semiPrime = generateSemiPrimeNumbers(n);
for (int i = 0; i < semiPrime.size(); i++)
cout << semiPrime[i] << "\t";
return 0;
}
Kết quả
Các số bán nguyên tố ≤ 15 là:
6 10 14 15