# UVA Problem 10924 – Prime Words Solution

UVA Problem 10924 – Prime Words Solution:

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 )
*/

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