计算所有小于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