**UVA Problem 10699 – Count the factors Solution:**

Click here to go to this problem in uva Online Judge.

**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[0] = primesTable[1] = 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; }