Đếm số gần nguyên tố từ 1 đến N trong C++

Cho N, đếm số gần nguyên tố (almost prime) từ 1 đến N. Số gần nguyên tố có đúng 2 ước số nguyên tố phân biệt. Ví dụ N=21 → 8.

Dùng sàng Eratosthenes tìm số nguyên tố. Với mỗi số, đếm số ước nguyên tố phân biệt, nếu bằng 2 thì tăng đếm.

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

Kết quả

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