同題：UVa 10699 – Count the factors
寫一個程式算出一個正整數有多少個不同的質因數。例如：45 = 335，所以 45 有 2 個質因數 (3 和 5）。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 每組測試資料一列。含有 1 個正整數 N (1 < N <= 1000000）。 若 N = 0 代表輸入結束。 | 對每組測試資料輸出一列，N 有多少個不同的質因數。輸出格式請參考 Sample Output。 |
| 7 8 45 289384 930887 692778 636916 747794 238336 885387 760493 516650 641422 0 | 7 : 1 8 : 1 45 : 2 289384 : 3 930887 : 2 692778 : 5 636916 : 4 747794 : 3 238336 : 3 885387 : 2 760493 : 2 516650 : 3 641422 : 3 |
解題思路
可以創建一個函式去判斷一個數字是否為質數。使用 For迴圈 從 2 到 N，如果找到 N 的因數就判斷其是否為質數，如果是質數就將答案 +1。
範例程式碼－ZeroJudge D120: Count the factors
#include <iostream>
#include <math.h>
using namespace std;
bool isPrime(int N) {
for (int i = 2; i<int(sqrt(N)+1); i++) {
if (N % i == 0) return false;
}
return true;
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
while (cin >> N && N != 0) {
int ans = 0;
for (int i = 2; i<=N; i++) {
if (N % i == 0 && isPrime(i)) {
ans++;
}
}
cout << N << " : " << ans << "\n";
}
}
//ZeroJudge D120
//Dr. SeanXD