Tìm số lượng gần như nguyên tố từ 1 đến N trong C ++

Giả sử chúng ta có một số N. Chúng ta phải tìm các số gần như nguyên tố trong phạm vi từ 1 đến N. Một số được gọi là gần như nguyên tố khi nó có đúng hai thừa số phân biệt. Các số có thể có bất kỳ số thừa số nguyên tố nào, nhưng phải là hai thừa số nguyên tố. Vì vậy, nếu N là 2, thì đầu ra sẽ là 2. Có hai số 6 và 10.

Ở đây chúng tôi sẽ sử dụng phương pháp tiếp cận Sieve of Eratosthenes. Vui lòng kiểm tra cách triển khai sau để có ý tưởng tốt hơn.

Ví dụ

#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);
}

Đầu ra

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