## Algorithm

Write a program, that computes the number of different prime factors in a positive integer. Input The input tests will consist of a series of positive integers. Each number is on a line on its own. The maximum value is 1000000. The end of the input is reached when the number ‘0’ is met. The number ‘0’ shall not be considered as part of the test set. Output The program shall output each result on a line by its own, following the format given in the sample output.

Sample Input 289384 930887 692778 636916 747794 238336 885387 760493 516650 641422 0

Sample Output 289384 : 3 930887 : 2 692778 : 5 636916 : 4 747794 : 3 238336 : 3 885387 : 2 760493 : 2 516650 : 3 641422 : 3

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````#include <bits/stdc++.h>

using namespace std;
#define N 1000001
#define ll long long
vector<int> numDiffPF;

// compute num of different PF each number have
void modifiedSieve(){
numDiffPF.assign(N, 0);
for(long long i=2;i i+It N;i++){
if(numDiffPF[i] == 0) {
for(long long j=i;j i+It N;j+=i)
numDiffPF[j]++;
}
}
}

int main()
{
modifiedSieve();
int v;
while(scanf("%d",&v),v){
printf("%d : %d\n",v,numDiffPF[v]);
}
}
```
```
Copy The Code &

Input

cmd
289384
930887
692778
636916
747794
238336
885387
760493
516650
641422

Output

cmd
289384 : 3
930887 : 2
692778 : 5
636916 : 4
747794 : 3
238336 : 3
885387 : 2
760493 : 2
516650 : 3
641422 : 3