Saturday, March 28, 2015

10924 - Prime Words (UVa)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define MAX 1500
#define size 241
int prime[size];
int status[MAX];

void getPrime()
{
    int i, j, p;
    int n = MAX;
    int sq = int(sqrt(n));
    for(i=3; i<=sq; i+=2)
    {
        if(status[i]==0)
        {
            for(j=i*i; j<=n; j+=(i+i))
            {
                status[j]=1;
            }
        }
    }
    prime[1]=1;
    prime[2]=2;
    p=3;
    for(i=3; i<=n ; i+=2)
    {
        if(status[i] == 0)
        {
            prime[p++] = i;
        }
    }
}

int binarySearch(int val)
{
    int start = 0, end = size;
    while(start<=end)
    {
        int mid =(start+end)/2;
        if(prime[mid]==val)
            return mid;
        else if(val<prime[mid])
            end = mid-1;
        else
            start = mid+1;
    }
    return -1;
}

int main()
{
   getPrime();
   string s;
   int i, sum;
   while(cin >> s)
   {
       cin.ignore();
       int len = s.length();
       sum = 0;
       for(i=0; i<len; i++)
       {
           if(s[i]>='a' && s[i] <='z')
           {
               sum += (s[i]-'a')+1;
           }
           else
           {
               sum += (s[i]-'A')+27;
           }

       }
       if(binarySearch(sum)==-1)
       {
            printf("It is not a prime word.\n");
       }
       else
       {
            printf("It is a prime word.\n");
       }
   }
}

No comments:

Post a Comment

Compare equality of two string in C

#include <stdio.h> #include<string.h> int main() {     char* country = "Bangladesh";     char* country2;     ...