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