นับจำนวน Almost Prime จาก 1 ถึง N ใน C++

สมมติว่ามีตัวเลข N เราต้องหาจำนวนเฉพาะเกือบ (Almost Prime) ในช่วง 1 ถึง N ตัวเลขจะเรียกว่า Almost Prime เมื่อมันมีตัวประกอบเฉพาะ (Prime Factors) ที่แตกต่างกันพอดีสองตัว ตัวเลขอาจมีตัวประกอบไม่ใช่เฉพาะได้เท่าไหร่ก็ได้ แต่ควรจะมีตัวประกอบเฉพาะสองตัว ดังนั้นถ้า N คือ 2 ผลลัพธ์จะเป็น 2 มีสองตัวเลขคือ 6 และ 10

ที่นี่เราจะใช้วิธี Sieve of Eratosthenes โปรดตรวจสอบการนำไปใช้ต่อไปนี้เพื่อเข้าใจได้ดีขึ้น

ตัวอย่าง

#include <iostream> 
#define N 100005 
using namespace std; 

bool prime[N];

void SieveOfEratosthenes() {
    for (int i = 0; i < N; i++)
        prime[i] = true;
    prime[1] = false;
    for (int i = 2; i * i < N; i++) {
        if (prime[i] == true) {
            for (int j = i * 2; j < N; j += i)
                prime[j] = false;
        }
    }
}

int countAlmostPrime(int n) {
    int result = 0;
    for (int i = 6; i <= n; i++) {
        int div_count = 0;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                if (j * j == i) {
                    if (prime[j])
                        div_count++;
                } else {
                    if (prime[j])
                        div_count++;
                    if (prime[i / j])
                        div_count++;
                }
            }
        }
        if (div_count == 2)
            result++;
    }
    return result;
}

int main() {
    SieveOfEratosthenes();
    int n = 21;
    cout << "Number of almost primes in range 1 to " << n << " is: " << countAlmostPrime(n);
}

ผลลัพธ์

Number of almost primes in range 1 to 21 is: 8