数据结构
网络
RDBMS
操作系统
Java
MS Excel
IOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究在 C++ 中查找 1 到 N 中的几乎素数
假设我们有一个数字 N。我们必须在范围 1 到 N 中查找几乎素数。当一个数字恰好有两个不同的因子时，它被称为几乎素数。这些数字可以拥有任意数量的非素数因子，但必须有两个素数因子。因此，如果 N 为 2，那么输出将为 2。有两个数字 6 和 10。
这里我们将采用埃拉托斯特尼筛法。请查看以下实现以获得更好的想法。
示例
#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
更新于：18-12-2019
298 次浏览
广告