ในปัญหานี้ เราได้รับจำนวนเต็ม N และเราต้องพิมพ์ตัวเลขกึ่งไพรม์ทั้งหมดที่น้อยกว่าหรือเท่ากับ N
ก่อนแก้ปัญหานี้ เรามาทำความเข้าใจว่าจำนวนกึ่งไพรม์คืออะไร
เลขกึ่งเฉพาะ เป็นตัวเลขที่มีค่าเป็นผลคูณของจำนวนเฉพาะที่แตกต่างกันสองจำนวน
มาดูตัวอย่างกัน
21 =3*7 เป็นจำนวนกึ่งไพรม์
25 =5*5 ไม่ใช่จำนวนกึ่งไพรม์
ตอนนี้ มาดูตัวอย่างตัวเลขกึ่งไพรม์ที่น้อยกว่าหรือเท่ากับ n
Input: N = 15 Output: 6 10 14 15
ในการแก้ปัญหานี้ เราต้องใช้ตัวเลขแต่ละตัวที่น้อยกว่าเท่ากับ N และตรวจสอบว่ามีตัวประกอบเฉพาะที่แตกต่างกันสองตัวหรือไม่
เคล็ดลับ − เรายังสามารถเริ่มอัลกอริทึมของเราจาก 6 ได้ด้วย เนื่องจากจำนวนกึ่งไพรม์ที่เล็กที่สุดคือ 6
ตัวอย่าง
#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<<"Semi-prime numbers less that or equal to "<<n<<"are :\n";
vector<int>semiPrime = generateSemiPrimeNumbers(n);
for (int i = 0; i < semiPrime.size(); i++)
cout<<semiPrime[i]<<"\t";
return 0;
} ผลลัพธ์
จำนวนกึ่งไพรม์ที่น้อยกว่าหรือเท่ากับ 15 คือ −
6 10 14 15
