Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1640
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 &
Try With Live Editor
Input
930887
692778
636916
747794
238336
885387
760493
516650
641422
Output
930887 : 2
692778 : 5
636916 : 4
747794 : 3
238336 : 3
885387 : 2
760493 : 2
516650 : 3
641422 : 3
Demonstration
UVA Online Judge solution - 10699-Count the factors - UVA Online Judge solution in C,C++,java