พิมพ์ Semi-Prime Numbers ทั้งหมดน้อยกว่าหรือเท่ากับ N ใน C++

ในปัญหานี้ เราจะได้รับจำนวนเต็ม N และต้องพิมพ์ Semi-Prime Numbers ทั้งหมดที่น้อยกว่าหรือเท่ากับ N

ก่อนแก้ปัญหา เรามาทำความเข้าใจก่อนว่า Semi-Prime Number คืออะไร

Semi-Prime Number คือ จำนวนที่มีค่าเป็นผลคูณของจำนวนเฉพาะ 2 ตัวที่ต่างกัน

ตัวอย่าง

21 = 3×7 เป็น Semi-Prime Number

25 = 5×5 ไม่ใช่ Semi-Prime Number

ตัวอย่าง Semi-Prime Numbers น้อยกว่าหรือเท่ากับ N:

Input: N = 15
Output: 6 10 14 15

เพื่อแก้ปัญหานี้ เราต้องนำแต่ละจำนวนที่น้อยกว่าหรือเท่ากับ N ไปตรวจสอบว่ามีตัวประกอบเฉพาะที่ต่างกันพอดี 2 ตัวหรือไม่

Tip - เราสามารถเริ่มอัลกอริทึมจาก 6 ได้ เพราะ Semi-Prime Number ที่เล็กที่สุดคือ 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;
}

ผลลัพธ์

Semi-prime numbers less than or equal to 15 are -

6 10 14 15