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

UVA Problem 543 – Goldbach’s Conjecture Solution

UVA Problem 543 – Goldbach’s Conjecture Solution:


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

Solving Technique:

First thing to notice is that value of n is always even and range to 1000000. Using naive approach will take a lot of time to check a if number is prime for each iteration.

We can cut down the time using Sieve of Eratosthenes to pre caculate prime numbers from 0 to 1000000 and store them in look up table. So each time we need to check if a number is prime just go to that index a see it the value stored is 1.

The problem statement specifically to find two prime numbers whose sum is equal to n and the difference of these two prime numbers be maximized.

As the conjecture states any even number greater than 4 is sum of two primes. But here the input start from 6 and specifically states that the sum have to be of two odd primes. Since 2 is an even prime it can’t be used.

Now there are multiple odd primes that may add up to n but since the difference between these primes need to be maximized we will always start with the smallest prime number.

For example,

n = a + b \\   \\  for, n = 42, \\   \\  42 = 5 + 37 \\  42 = 11 + 31 \\  42 = 13 + 29 \\  42 = 19 + 23 \\  42 = 23 + 19 \\  42 = 29 + 13 \\  42 = 31 + 11 \\  42 = 37 + 5 \\  \\  \text{From above,} \\  b - a, \\  \\  37 - 5 > 31 - 11 > 29 - 13 > 23 - 19 > 19 - 23 > 13 - 29 > 11 - 31 > 5 - 37  \\  \\  \text{when,} \\  a = a_{min} \\  b = b_{max} \\  \\  \text{then,} \\  \text{b - a is maximized} \\  \\  \text{So,} \\      n = a_{min} + b_{max} \\  b_{max} = n - a_{min} \\    

Since, we know n, now try prime numbers from 3 to \frac{n}{2} as a and b = n - a , when a is prime.
If, b is also a prime then we got our answer and no longer need to calculate. Now print the answer.

Odd prime that make up 42 are,

UVA 543 Goldbachs Conjecture Diagram
UVA 543 Goldbachs Conjecture Diagram

 

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++.


Input:

8
20
42
0

 


Output:

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

Code:

/**
 * Author:     Quickgrid ( Asif Ahmed )
 * Site:       https://quickgrid.wordpress.com
 * Problem:    UVA 543 - Goldbach's Conjecture
 * Techniques: Primality Test, Prime Number Generation.
 */

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

#define N 1000000

/**
 * Since value can be up to 1000000
 */
int primesTable[N];

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 * i; k <= N; k += i )
                primesTable[k] = 0;
        }
    }

    /**
     * 2 is an Even Prime but the question states only odd primes,
     * So 2 should be left out.
     */
    primesTable[2] = 0;

}

int main() {

    SieveOfEratosthenes();

    int n;

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

        /**
         * The bound here does not matter much. a < ( n >> 1 ) will also work.
         * But no need for that, max(n) = b - a will be always found before n / 2 for this problem.
         *
         * Since we are maximizing and starting with the lowest value and
         * generating the larger value from that so a and b will be at most n / 2.
         *
         * If, a + b = n, then if a > n / 2 then, b < n / 2 otherwise a + b != n.
         *
         * Also start from 3 since 2 is an even prime and not allowed in this problem.
         */
        for(int a = 3; a < n; ++a){

            if( primesTable[a] ){

                /**
                 * Since, n = a + b
                 * Them,  b = n - a
                 */
                int b = n - a;

                /**
                 * Check if the resulting number is prime since a and b both are primes.
                 * A number may be made up of multiple primes but print the first one since
                 * we are asked to maximize b - a.
                 */
                if( primesTable[b] ){
                    printf("%d = %d + %d\n", n, a, b);
                    break;
                }

            }
        }

    }


    return 0;
}

UVA Problem 10924 – Prime Words Solution

UVA Problem 10924 – Prime Words Solution:


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

Solving Technique:

This problem is easy we just need to read it carefully.

The problem assigns values for 1 to 26 for (a-z) and 27 – 52 for (A-Z). The input is a stringWe are asked to find the sum of every character with given value and check if the sum is a prime number or not.  

Summing is actually easy. For lower case when we sum, we just subtract the character from ASCII value of a or the ‘a’ character. This way we get 1 to 25 for ( a to z ). Since the number that was assigned was 1 more, so we add 1 to every value in loop. We do the same thing for upper case letters ( subtract ‘A’ from each character ). So we get 0 to 25 again. This time we add 27 to every value in loop so we get 27 to 52 for ( A to Z ).

One important thing to note is although 1 is not a prime. In this problem it is specified that it is prime. We output according to given specification.  So if the sum of all given word is 1 then the output is prime. Ex, a ( since a is 1 ).

The given word length is 1 to 20. So an array of 21 is enough. We should check for EOF to terminate the program.

Important:  Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Critical Inputs:

UFRN
contest
AcM
a

Output:

It is a prime word.
It is not a prime word.
It is not a prime word.
It is a prime word.

Code (using lookup table, Sieve of Eratosthenes):

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

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

/**
 * Since there is max of 20 characters in a single line
 * Calculating with biggest value 'Z' gives a max of 1040
 */
#define N 1041

static int table[128];
static unsigned primes[N];

void PreSum(){
    register unsigned i, j = 1;

    /**
     * Set 1 to 26 for 'a' to 'z'
     */
    for (i = 'a'; i <= 'z'; ++i, ++j)
        table[i] = j;

    /**
     * Set 27 to 52 for 'a' to 'z'
     */
    for (i = 'A'; i <= 'Z'; ++i, ++j)
        table[i] = j;
}

void SieveOfEratosthenes(){
    register unsigned i, j;

    /**
     * For this problem though 0 and 1 are primes
     */
    for (i = 0; i < N; ++i)
        primes[i] = 1;

    unsigned len = sqrt(N);

    for (i = 2; i <= len; ++i){
        if (primes[i]){
            for (j = i * i; j <= N; j += i)
                primes[j] = 0;
        }
    }
}

int main(){
    /**
     * Pre calculate character value table
     * Pre calculate prime values using Sieve of Eratosthenes
     */
    PreSum();
    SieveOfEratosthenes();

    char s[32];
    register unsigned i;

	while (gets(s)){
        unsigned sum = 0;

        /**
         * Get character value from pre calculated character value table and sum them
         */
        for (i = 0; s[i]; ++i)
            sum += table[s[i]];

        /**
         * Get primality from pre calculated prime table
         */
        if (primes[sum])
            printf("It is a prime word.\n");
        else
            printf("It is not a prime word.\n");
	}
	return 0;
}

Code (without using table):

/*
 * Author: Quickgrid ( Asif Ahmed )
 * Site: https://quickgrid.wordpress.com
 */

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

static char s[32];

int main(){
    while (gets(s)){
        unsigned int i, sum = 0;

        for (i = 0; s[i]; ++i){
            if (s[i] >= 'a' && s[i] <= 'z')
                sum += s[i]-'a'+1;
            else
                sum += s[i]-'A'+27;
        }

        if (sum <= 2)
            printf("It is a prime word.\n");
        else if (sum % 2 == 0)
            printf("It is not a prime word.\n");
        else{
            unsigned int prime = 1, len = sqrt(sum);
            for(i = 3; i <= len; i += 2){
                if(sum % i == 0){
                    printf("It is not a prime word.\n");
                    prime = 0;
                    break;
                }
            }
            if (prime)
                printf("It is a prime word.\n");
        }
    }
    return 0;
}

UVA Problem 10235 ( Simply Emirp ) Solution

UVA Problem 10235 ( Simply Emirp ) Solution:


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

Solving Technique:

Rank 115, Run time 0.012 s ( 12 ms ).

I have solved this problem in two ways first one is optimized primality test and second one is Sieve of Eratosthenes.

Problem is simple with a is simple we need to check if it’s prime or not. If it is then is it emrip or just prime.

There is one critical example that wasn’t given, its given below. If a prime is reversed and the reversed number is also prime then it is emrip. Ex, 17 is prime and reverse of 17 is 71 is also prime, then 17 is emrip.

If the number is emrip we should print emrip instead prime.

Critical example: 383 is prime but not emrip. If the number is prime and reversed number is equal to original number then it is not emrip.

Important:  Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Code Explanation:

I’ve written a custom check prime function to check for primes since it’ll be called twice. If the number is prime then I reversed the number and checked if that number is also prime. Lastly I checked if the reversed number is prime and also reversed number not equal to original.


Critical Input:

999
481184
373
998001
998857
753257
823455
999999
850058
78887
999983

Output:

999 is not prime.
481184 is not prime.
373 is prime.
998001 is not prime.
998857 is emirp.
753257 is prime.
823455 is not prime.
999999 is not prime.
850058 is not prime.
78887 is prime.
999983 is emirp.

Code:

/*
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10235 ( Simply Emrip optimized primality )
 */

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

unsigned int checkPrime(unsigned int n){
    if (n == 2)
        return 1;

    if (n % 2 == 0 || n < 2)
        return 0;

    register unsigned int i;
    unsigned int len = sqrt(n);

    for (i = 3; i <= len; i += 2){
        if (n % i == 0)
            return 0;
    }

    return 1;
}

int main(){
    register unsigned int n;
    unsigned int p, prime, mod;

    while (scanf("%u", &n) == 1){

        /**
         * check if number is prime
         */
        p = checkPrime(n);  

        if (p){
            /**
             * Reverse prime
             */
            prime = n;
            mod = 1;

            while (prime / mod){
                mod *= 10;
            }
            mod /= 10;

            unsigned int reversePrime = 0;
            while (prime){
                /**
                 * Here reversePrime is the reversed prime
                 */
                reversePrime += mod * (prime % 10);
                prime /= 10;
                mod /= 10;
            }
            /**
             * Reverse prime end
             */

            if (checkPrime(reversePrime) && reversePrime != n){  /* check if reverse is prime but also check the reversed number does not match the original */
                printf("%u is emirp.\n", n);
            }else{
                printf("%u is prime.\n", n);
            }
        }else{
            printf("%u is not prime.\n", n);
        }
    }
    return 0;
}

 

Simply Emrip with Sieve of Eratosthenes:

/*
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 10235 ( Simply Emrip Sieve of Eratosthenes)
 */

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

#define N 1000000

/**
 * Since value can be up to 1000000
 */
unsigned int *primes = new unsigned int[N]; 

unsigned int *SieveOfEratosthenes(unsigned int n){
    register unsigned int i = 2;

    for (; i <= n; ++i)
        primes[i] = 1;

    primes[0] = primes[1] = 0;
    unsigned int len = sqrt(n);

    for (i = 2; i <= len; ++i){
        if (primes[i]){
            for (unsigned int k = i * i; k <= n; k += i)
                primes[k] = 0;
        }
    }
    return primes;
}

int main(){
    register unsigned int n;
    unsigned int prime, mod;

    /**
     * Pre calculate sieve for every value
     */
    primes = SieveOfEratosthenes(N);    

    while (scanf("%u", &n) == 1){
        if (primes[n]){                  /* Since sieve is calculated and stored on table just do a look up */

            prime = n;
            mod = 1;

            while (prime / mod){
                mod *= 10;
            }
            mod /= 10;

            unsigned int reversePrime = 0;
            while (prime){
                reversePrime += mod * (prime % 10);
                prime /= 10;
                mod /= 10;
            }

            /**
             * Again access table to see if it is a prime
             */
            if (primes[reversePrime] && reversePrime != n)
                printf("%u is emirp.\n", n);
            else
                printf("%u is prime.\n", n);
        }else
            printf("%u is not prime.\n", n);
    }
    return 0;
}