10235 - Simply Emirp

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 1000000
#define size 79000
#define pf printf
long long status[MAX];
int prime[size];


void getPrime()
{
    int i, j, p;
    long long n = MAX;
    int sq = 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]=2;
    p=2;
    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 rev(int num)
{
    int revPrime=0;
    while(num>0)
    {
        revPrime *=10;
        revPrime += num%10;
        num/=10;
    }
    return revPrime;
}

int main()
{
    int n, rev_n;
    getPrime();
    while(scanf("%d", &n)==1)
    {
        if(binarySearch(n)!=-1)
        {
            rev_n = rev(n);
            if(binarySearch(rev_n)!=-1 && n!=rev_n)
                pf("%d is emirp.\n", n);
            else
                pf("%d is prime.\n", n);
        }
        else
        {
           pf("%d is not prime.\n", n);
        }
    }
    return 0;
}