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

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