ค้นหาจำนวนเลขเด่นจาก 1 ถึง N ใน C++

สมมติว่าเรามีตัวเลข N เราต้องหาจำนวนเฉพาะที่ใกล้เคียงที่สุดในช่วง 1 ถึง N ตัวเลขนี้เรียกว่าเกือบเฉพาะเมื่อมีตัวประกอบที่แตกต่างกันสองตัวพอดี ตัวเลขสามารถมีตัวประกอบที่ไม่ใช่เฉพาะจำนวนเท่าใดก็ได้ แต่ควรเป็นปัจจัยเฉพาะสองตัว ดังนั้นถ้า 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