计算所有小于10 ^ 6的最小素数为N C ++的数字
我们给定一个质数，例如num，任务是计算所有小于10^6且最小质数等于num的数字的计数。
例如
Input − num = 7Output − Number of prime factors = 38095Input − num = 3Output − Number of prime factors = 16666
以下程序中使用的方法如下
输入数字，例如num
从i到2开始循环，并且i应当小于或等于最大值并增加i的值
在循环内部，检查s_prime[i]=0
创建循环，将j设置为i*2，并且j应当小于等于max，并将j设置为j+i
现在检查s_prime[j]=1
设置s_prime[j]=1
s_count[i]增加1
打印结果
示例
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
//质数筛子
//计算素数
int s_prime[MAX + 4] = { 0 }, s_count[MAX + 4] = { 0 };
void create_sieve(){
//由于1不是质数
s_prime[1] = 1;
//创建筛子
for (int i = 2; i <= MAX; i++){
//如果我是素数
if (s_prime[i] == 0){
for (int j = i * 2; j <= MAX; j += i){
//如果我是最不重要的因素
if (s_prime[j] == 0){
//数字j不是质数
s_prime[j] = 1;
//计算最小素数的数字
//我是
s_count[i]++;
}
}
}
}
}
int main(){
//创建筛子
create_sieve();
int N = 7;
cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
N = 3;
cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
return 0;
}输出结果
如果我们运行上面的代码，它将生成以下输出-
Number of prime factors = 38095 Number of prime factors = 166667