poj 2407 Relatives

這個題一看就知道是求歐拉函數。歐拉函數描述的正式題意。歐拉函數的理解可以按照算法導論上面的說法，對0-N-1進行篩選素數。
那麼公式n∏(1-1/p)，其中p是n的素數因子，就可以得到直觀的理解了。但是計算的時候，會將這個式子變形下，得到另外一個形式。
   如圖所示：

   但是這個題，需要考慮下，有可能n是個大素數，直接進行因子分解的話會超時的。怎麼辦了，只能在分解的時候判斷n是不是已經成為
素數了，如果是素數，答案再乘以n-1就行了。為了加快判斷，我用5mb的空間搞了個素數表，大於5000000的數字只能循環判斷了。

 代碼如下，注意求歐拉函數的代碼部分：
#include <stdio.h>
#include <math.h>
#define MAX (5000000)
bool bPrime[MAX];//false表示素數

void InitPrime()
{
    bPrime[0] = bPrime[1] = true;
    int nMax = sqrt((double)MAX) + 1;
    for (int i = 2; i <= nMax; ++i)
    {
        if (!bPrime[i])
        for (int j = i * 2; j < MAX; j += i)
        {
            bPrime[j] = true;
        }
    }
}

bool IsPrime(int nN)
{
    if (nN < MAX)
    {
        return !bPrime[nN];
    }
    else
    {
        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), nN)
    {
        if (nN == 1){printf("0\n");continue;}
        int nAns = 1;
        for (int i = 2; i <= nN; ++i)
        {
            if (IsPrime(nN))
            {
                nAns *= nN - 1;
                break;
            }
            if (nN % i == 0)
            {
                nAns *= i - 1;
                nN /= i;www.2cto.com
                while (nN % i == 0)
                {
                    nAns *= i;
                    nN /= i;
                }
            }
        }
        printf("%d\n", nAns);
    }
   
    return 0;
}