UVa 10699 – Count the factors
Write a program to calculate how many distinct prime factors a positive integer has. For example, 45 = 335, so 45 has 2 prime factors (3 and 5).
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| Each set of test data is in a single line containing a positive integer N (1 < N ≤ 1000000). If N = 0, it means the input has ended. | For each set of test data, output a line indicating the number of distinct prime factors of N. Please refer to the sample output for the output format. |
| 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 |
Thought Process
You can create a function to determine whether a number is prime. Use a for loop from 2 to N. If you find a factor of N, check if it's a prime number. If it's prime, increment the answer by 1.
Sample Code－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