アルゴリズムノート練習5.5素因数分解問題C:素因数の個数
12314 ワード
アルゴリズムノート練習問題解合集
タイトルリンク
タイトル
題目は正の整数N(N>1)の素因数の個数を求めることを説明します.同じ質量係数は繰り返し計算する必要がある.120=2235のように、5つの素因数がある.
入力には複数のテストデータがあり、各テストデータの入力は正の整数N、(1)
各セットのデータに対して、Nの素因数の個数を出力する.
サンプル入力
サンプル出力
ヒント1はNの素因数ではない.Nが素数であれば、NはNの素因数である.
構想
関数
コード#コード#
タイトルリンク
タイトル
題目は正の整数N(N>1)の素因数の個数を求めることを説明します.同じ質量係数は繰り返し計算する必要がある.120=2235のように、5つの素因数がある.
入力には複数のテストデータがあり、各テストデータの入力は正の整数N、(1)
各セットのデータに対して、Nの素因数の個数を出力する.
サンプル入力
120
200
サンプル出力
5
5
ヒント1はNの素因数ではない.Nが素数であれば、NはNの素因数である.
構想
関数
primeFactorization
の考え方は【PAT A 1059】Prime Factorsを参照してください.コード#コード#
#include
#include
#define MAX 50000
typedef struct {
int x, exp;
} Factor;
//
int isPrime[MAX], primeCnt = 0, primeTable[MAX/10];
int findPrime(void) {
int i, j;
for (i = 2; i < MAX; ++i)
isPrime[i] = 1;
for (i = 2; i < MAX; ++i) {
if (isPrime[i]) {
primeTable[primeCnt++] = i;
for (j = i; j < MAX; j += i)
isPrime[j] = 0;
}
}
}
// num , factors,
// num >= 2
int primeFactorization(int num, Factor *factors) {
int i, n = num; // n num
int factorCnt = 0;
for (i = 0; i < 10; ++i) //
factors[i].exp = 0;
for (i = 0; i < primeCnt; ++i) {
if ((int)sqrt((double)num) < primeTable[i])
break;
if (n % primeTable[i] == 0) {
factors[factorCnt].x = primeTable[i];
while (n % primeTable[i] == 0) {
n /= primeTable[i];
++factors[factorCnt].exp;
}
++factorCnt;
}
}
if (n != 1) {
factors[factorCnt].x = n;
factors[factorCnt].exp = 1;
++factorCnt;
}
return factorCnt;
}
int main() {
findPrime();
int N, i;
Factor factors[10];
while (scanf("%d", &N) != EOF) {
int cnt = 0;
int factorCnt = primeFactorization(N, factors);
for (i = 0; i < factorCnt; ++i)
cnt += factors[i].exp;
printf("%d
", cnt);
}
return 0;
}