# UVA Problem 10699 – Count the factors Solution

UVA Problem 10699 – Count the factors Solution:

Solving Technique:

The problem requirement is to find the prime factors of a given number. If the input number is divisible by a prime number then that prime number is a prime factor of input.

Similarly do this with all prime numbers less than the input if it is divisible then increase prime factor count. It seems like there is a way to cut down running time in this very code, but I am not able find it.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

```289384
930887
692778
636916
747794
238336
885387
760493
516650
641422
0
```

Output:

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

### Code:

```/**
* Author:    Asif Ahmed
* Site:      https://quickgrid.wordpress.com
* Problem:   UVA 10699 - count the factors
* Technique: Efficient Prime Generation, Sieve of Eratosthenes.
*/

#include<stdio.h>
#include<math.h>

/**
* Since value can be up to 1000000
*/

#define N 1000000

int primesTable[N];
int onlyPrimesTable[N];

int k = 0;

void SieveOfEratosthenes(){

int i = 2;

/**
* Set Every index in the table to be prime.
*/
for(; i <= N; ++i)
primesTable[i] = 1;

/**
* Base case 0 and 1 are not primes.
*/
primesTable = primesTable = 0;

int len = sqrt(N);

/**
* Set all multiples of a number to 0 since primes can't divisible by other than itself.
*/
for(i = 2; i <= len; ++i){
if(primesTable[i]){
for( int k = i << 1; k <= N; k += i )
primesTable[k] = 0;
}
}

/**
* This is not really a part of Sieve of Eratosthenes.
* It checks if a number is prime then it moves primes
* to another array which only contain primes and this
* reduces the number of lookups.
*/
for(i = 0; i <= N; ++i){
if(primesTable[i])
onlyPrimesTable[k++] = i;
}
}

int main() {

/**
* Pre generate primes and isolate them to another array.
*/
SieveOfEratosthenes();

int n;

/**
* Input the number and check if its 0.
*/
while(scanf("%d", &n) && n){

int c = 0;

/**
* If the number is divisible by a prime then,
* increase prime factor count.
*/

for(int i = 0; i < k; ++i){
if( n % onlyPrimesTable[i] == 0)
++c;
}

printf("%d : %d\n", n, c);

}

return 0;
}
```