UVA Problem 10699 – Count the factors Solution

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;
}

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s