poj 1284 Primitive Roots

這個題是求原根的個數。所謂原根，意思是給定一個數n，存在數g，g^j能夠產生乘法群Zn*中所有的數字。即g^j = {x|x與n互質,
1<=x<n}。如果n是奇素數p(大於2的素數)，那麼滿足g^j={1,2,...,p-1}。
   這個題目要求求原根的個數。由費馬定理由,對任意1<=x<p，即Zp*中的數字，都由x^(p-1) = 1 % p。從費馬定理可以看出，
再往下計算就開始循環了。那麼有,x^i%p(1<=i<p) = {1, 2, 3,...,p-1},意思是能夠生成Zp*中的所有數字。
   根據上面的那個式子可以得到，x^i%(p-1)(1<=i<p) = {0, 1, 2,...,p-2}。 如果由gcd(x,p-1) = 1,那麼必然存在某個x^i，
使得x^i*x = (p-1)%p。
   因此可以得到，原根的個數是p-1的乘法群中元素的個數，也就是歐拉函數(p-1)。

代碼如下：
  
#include <stdio.h>
#include <math.h>
#define MAX (5000000)
bool bPrime[MAX];
void InitPrime()
{
    int nMax = sqrt((double)MAX) + 1;
    bPrime[0] = bPrime[1] = true;
    for (int i = 2; i <= nMax; ++i)
    {
        if (!bPrime[i])
        {
            for (int j = 2 * i; j < MAX; j += i)
            {
                bPrime[j] = true;
            }
        }
    }
}
bool IsPrime(int nN)
{
    if (nN < MAX)return !bPrime[nN];
    int nMax = sqrt((double)nN) + 1;
    for (int i = 2; i <= nMax; ++i)
    {
        if (nN % i == 0)
            return false;
    }
    return true;
}
int main()
{
    int nN;
    InitPrime();
    while (scanf("%d", &nN) == 1)
    {
        nN--;
        int nAns = 1;
        if (IsPrime(nN))
        {
            nAns = nN - 1;
        }www.2cto.com
        else
        {
            for (int i = 2; i <= nN; ++i)
            {
                if (nN % i == 0)
                {
                    nAns *= i - 1;
                    nN /= i;
                    while (nN % i == 0)
                    {
                        nAns *= i;
                        nN /= i;
                    }
                    if (IsPrime(nN))
                    {
                        nAns *= nN - 1;
                        break;
                    }
                }
            }
        }
        printf("%d\n", nAns);
    }
    return 0;
}