ACM 10006 Carmichael Numbers

一開始以為只要算prime就好了，真是好天真，
馬上得到WA一枚。

Carmichael number的意思：
某數經由Fermat Test算出為質數，
但實際上為合數的數，就稱為Carmichael number。

也就是判斷n是否由Fermat Test算出來是質數，
但實際上是合數即可。

Fermat Test是關鍵，因為要算mod，
雖然跟ACM374，但我那題的解法在這題卻不適用。
一個比較好的算則是mod的分配律：
假設 (a * b) % m，可以拆為：
(a % m) * (b % m)。
同理，a^2 % m可以拆為，
(a % m) * (a % m)。
如此就可以把a^n一路往下拆，拆到n為1或0為止。
然而最大數為64998 ^ 2為4224740004，
所以要用unsigned。

有兩種作法，先算出1到65000的Carmichael number，
若測資為這些數，可直接做輸出。

第二種方法，直接做，但演算法要正確且快速，否則會TL。
判斷數字n是否是質數，是質數的情況下，必不為Carmichael number，
若n滿足Fermat Test，要再判斷n是否為質數。
C語言的&&運算子為short-circuit evaluation，
所以質數判斷放前面，Fermat Test判斷放後面，
會比較快。

/* ACM 10006 Carmichael Numbers
 * mythnc
 * 2011/11/14 16:53:51   
 * run time: 0.144
 */
#include <stdio.h>

#define FALSE 0
#define TRUE  1

int prime(int);
int fermat(int);
unsigned int powermod(int a, int n, int d);

int main(void)
{
    int n;

    while (scanf("%d", &n) && n != 0)
        if (!prime(n) && fermat(n))
            printf("The number %d is a Carmichael number.\n", n);
        else
            printf("%d is normal.\n", n);

    return 0;
}

/* fermat: do Fermat test,
 * if n is prime return TRUE,
 * else return FALSE.
 * WARNING: it means in Fermat test is a prime,
 * maybe it isn't really a prime */
int fermat(int n)
{
    int i;

    for (i = 2; i < n; i++)
        if (powermod(i, n, n) != i)
            return FALSE;

    return TRUE;
}

/* powermod: calculate mod value,
 * in recursive method,
 * return big mod number */
unsigned int powermod(int a, int n, int d)
{
    unsigned int x;

    if (n == 0)
        return 1;
    if (n == 1)
        return a % d;
    
    x = powermod(a, n / 2, d);
    x = x * x % d;
    if (n % 2 == 0)
        return x;
    else
        return x * a % d;
}

/* prime: return TRUE if n is prime,
 * else return FALSE */
int prime(int n)
{
    int i;

    for (i = 3; i * i <= n; i++)
        if (n % i == 0)
            return FALSE;

    return TRUE;
}