C ++中最大唯一质数的数量

  • Z时代
  • 2024-01-10
  • 分类：综合

给定任务是找到一个最大素数，该素数可以在[1，N]的范围内给出N。

现在让我们使用示例了解我们必须做的事情-

输入-N = 100

输出-3

说明-让我们在[1，100]范围内取30

30 = 3 * 2 * 5 =唯一素因数。因此，在[1，100]范围内，最多可以找到3个唯一因子。

输入-N = 300

输出-4

在以下程序中使用的方法如下

  • 在功能上，MaxPrime()我们将首先检查（N <2）。如果是这样，则只需返回零，否则继续。

  • 然后，我们将使用Eratosthenes筛子找出给定数字N之前的所有素数。

  • 初始化两个int类型的变量pro = 1和max = 0分别存储乘积和最终答案。

  • 在Eratosthenes的筛子中，我们将第一组素数相乘，直到乘积保持小于N为止，方法是：-pro = * p;

  • 检查是否（pro> N）。如果是这样，则返回max并将max加1。

  • 在筛子外面，也返回最大值。

示例

#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N){
   if (N < 2)
      return 0;
   //使用Eratosthenes筛
   bool Arr[N+1];
   memset(Arr, true, sizeof(Arr));
   int pro = 1, max = 0;
   for (int p=2; p*p<=N; p++){
      if (Arr[p] == true){
         for (int i=p*2; i<=N; i += p)
            Arr[i] = false;
         /*Multiply first set of prime numbers while product remains smaller than N*/
         pro *= p;
         if (pro > N)
            return max;
         max++;
      }
   }
   return max;
}
//主要功能
int main(){
   int N = 300;
   cout << MaxPrime(N);
   return 0;
}

输出结果

如果运行上面的代码，我们将获得以下输出-

4

以上是 C ++中最大唯一质数的数量 的全部内容， 来源链接： utcz.com/z/338152.html

回到顶部