Solution of 10235 - Simply Emirp

Problem Description
source:https://uva.onlinejudge.org/external/102/10235.html

An integer greater than 1 is called a prime number if its only positive divisors (factors) are 1 and itself. Prime numbers have been studied over the years by a lot of mathematicians. Applications of prime numbers arise in Cryptography and Coding Theory among others. 
      Have you tried reversing a prime? For most primes, you get a composite (43 becomes 34). An Emirp (Prime spelt backwards) is a Prime that gives you a different Prime when its digits are reversed. For example, 17 is Emirp because 17 as well as 71 are Prime. 
     In this problem, you have to decide whether a number N is Non-prime or Prime or Emirp. Assume that 1 < N < 1000000. 
     Interestingly, Emirps are not new to NTU students. We have been boarding 199 and 179 buses for quite a long time! 

Input 

Input consists of several lines specifying values for N. 

Output 

For each N given in the input, output should contain one of the following: 
     1. ‘N is not prime.’, if N is not a Prime number. 
     2. ‘N is prime.’, if N is Prime and N is not Emirp. 
     3. ‘N is emirp.’, if N is Emirp. 

Sample Input 

17 
18 
19 
179 
199 

Sample Output 

17 is emirp. 18 is not prime. 
19 is prime. 
179 is emirp. 
199 is emirp.

Solution:

#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include<stdio.h>
#include<stdlib.h>
#define max 1000002

using namespace std;

void GenPrime();
long int Reverse(long int p);
long int prime[max];

int main()
{
    GenPrime();
    long int n,rev,tem;
    while(scanf("%ld",&n)==1)
    {
        rev=Reverse(n);
        if(prime[n] && prime[rev]&& n>9 && rev!=n)
            printf("%ld is emirp.\n",n);
        else if(prime[n])
            printf("%ld is prime.\n",n);
        else
            printf("%ld is not prime.\n",n);
    }
    return 0;

}
void GenPrime()
{
    long int i,j,m;
    m=(long int)sqrt(max);
    memset(prime, 1, sizeof(prime));
    prime[0]=prime[1]=0;
    for(i=2;i<=m;i++)
    {
        if(prime[i])
            for(j=i+i;j<max;j+=i)
                prime[j]=0;
    }

}
long int Reverse(long int p)
{
    long int r;
    r=0;
    while(p!=0)
    {
        r=(r*10)+(p%10);
        p=p/10;
    }
    return r;
}