C++プログラムの素因数

プライムファクター は与えられた数の因数である素数です。

数値の要因 は、与えられた数を得るために乗算される数です。

プライム因数分解 は、数をその素因数で再帰的に除算して、その数のすべての素因数を見つけるプロセスです。

Example :
N = 120
Prime factors = 2 5 3
Factorization : 2 * 2 * 2 * 3 * 5

数の素因数について覚えておくべきいくつかのポイント

• 数の素因数のセットは一意です。
• 因数分解は、除算、共通の分母の検索など、多くの数学計算で重要です。
• これは暗号化における重要な概念です。

数の素因数を見つけるプログラム

例

#include <iostream>
#include <math.h>
using namespace std;
void printPrimeFactors(int n) {
   while (n%2 == 0){
      cout<<"2\t";
      n = n/2;
   }
   for (int i = 3; i <= sqrt(n); i = i+2){
      while (n%i == 0){
         cout<<i<<"\t";
         n = n/i;
      }
   }
   if (n > 2)
   cout<<n<<"\t";
}
int main() {
   int n = 2632;
   cout<<"Prime factors of "<<n<<" are :\t";
   printPrimeFactors(n);
   return 0;
}

出力

Prime factors of 2632 are :2   2   2   7   47