ACM 10235 Simply Emirp

如何判斷n是不是質數？
最簡單的方法就是2到n-1去除n，
若能被整除，那就不是質數。
但在實作上不會這麼笨，只要從2到√n就可以了。
因為如果n是合數，n就可以拆成2個數字，
而其中一個數字，會<=√n。

/* ACM 10235
 * mythnc
 * 2011/10/15 13:29:01   
 * run time: 0.012
 */
#include <stdio.h>

#define PRIME 1
#define NOT_P 0

int prime(int);
int reverse(int);

int main(void)
{
    int n;

    while (scanf("%d", &n) != EOF) {
        if (prime(n))
            if (reverse(n))
                printf("%d is emirp.\n", n);
            else
                printf("%d is prime.\n", n);
        else
                printf("%d is not prime.\n", n);
    }
    return 0;
}

/* prime: judge n is prime or not */
int prime(int n)
{
    int i;

    if (n == 2)           /* 2 is prime */
        return PRIME;
    if (n % 2 == 0)       /* even is not prime */
        return NOT_P;
    for (i = 3; i * i <= n; i++)
        if (n % i == 0)
            return NOT_P;
    return PRIME;
}

/* reverse: return prime(the reverse n) */
int reverse(int n)
{
    int x, tmp;

    tmp = n;
    x = n % 10;
    while ((n /= 10) > 0) {
        x *= 10;
        x += n % 10;
    }
    if (x == tmp)    /* if reverse n is the same n */
        return 0;    /* can't output emirp */
    return prime(x);
}