在C ++中查找从1到N的几乎素数的计数
假设我们有一个数字N。我们必须找到1到N范围内的几乎素数。一个数字恰好具有两个截然不同的因子，就称为几乎素数。数字可以具有任意数量的非素数，但应为两个素数。因此，如果N为2，则输出将为2。有两个数字6和10。
在这里，我们将使用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