[zerojudge] d387: 10235 - Simply Emirp

from sys import stdin

def isPrime(n):
    '''
    參考 http://www.csie.ntnu.edu.tw/~u91029/Prime.html
    質數判定
    ''' 
    if(n == 2): return 1
    if(n%2 == 0): return 0
    if(n%6 not in [1,5]): return 0
    u = n - 1
    t = 0
    while(u % 2 == 0):
        u >>= 1
        t += 1
    sprp = [2, 7, 61]
    for sk in sprp:
        a = sk % n
        if (a == 0 or a == 1 or a == n-1): continue
        x = pow(a, u, n)
        if (x == 1 or x == n-1): continue
        for i in range(t-1):
            x = pow(x, 2, n)
            if (x == 1): return 0
            if (x == n-1): break
        if (x != n-1): return 0
    return 1

ans = ['not prime.', 'prime.', 'emirp.']

for s in stdin:
    s = s.strip()
    sr = s[::-1]
    v = isPrime(int(s))
    # 先檢查 int(s) 是否為質數 
    if(v and sr != s):
        # s 是質數才檢查 sr
        v += isPrime(int(sr))
    print('{} is {}'.format(s, ans[v]))