C ++中大量的素数

在这个问题中，我们得到一个整数N <= 10 ^ 18。我们的任务是打印数字的所有素数以及出现的频率。

让我们举个例子来了解这个问题，

Input: 100
Output: 2 2
   5 2
Explanation: prime factorization of 100 = 2 * 2 * 5 * 5.

为了解决这个问题，我们将不得不找到数字的素因，然后计算它们的频率。

为此，我们将检查2的频率作为一个因子，并将其除以2。然后从3到平方根n进行检查。除并增加每个质数的频率，质数是该因子的一个因数。如果数字变为1，则停止。然后以该频率打印所有质数。

以下代码显示了我们解决方案的实现，

示例

#include <iostream>
#include <math.h>
using namespace std;
void factorize(long long n){
   int count = 0;
   while (!(n % 2)) {
      n/= 2;
      count++;
   }
   if (count)
      cout<<2<<"\t"<<count<<endl;
   for (long long i = 3; i <= sqrt(n); i += 2) {
      count = 0;
      while (n % i == 0) {
         count++;
         n = n / i;
      }
      if (count)
      cout<<i<<"\t"<<count<<endl;
   }
   if (n > 2)
   cout<<n<<"\t"<<1<<endl;
}
int main() {
   long long N = 21000;
   cout<<"The prime factors and their frequencies of the number "<<N<<" are \n";
   factorize(N);
   return 0;
}

输出结果

The prime factors and their frequencies of the number 21000 are
2   3
3   1
5   3
7   1