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

x
–
+
cmd
289384
930887
692778
636916
747794
238336
885387
760493
516650
641422

Output

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

Demonstration

UVA Online Judge solution - 10699-Count the factors - UVA Online Judge solution in C,C++,java

Previous
UVA Online Judge solution - 10698-Football Sort - UVA Online Judge solution in C,C++,java
Next
UVA Online Judge solution - 10706-Number Sequence - UVA Online Judge solution in C,C++,java