poj 1284 Primitive Roots

这个题是求原根的个数。所谓原根，意思是给定一个数n，存在数g，g^j能够产生乘法群Zn*中所有的数字。即g^j = {x|x与n互质,
1<=x 这个题目要求求原根的个数。由费马定理由,对任意1<=x 再往下计算就开始循环了。那么有,x^i%p(1<=i 根据上面的那个式子可以得到，x^i%(p-1)(1<=i 使得x^i*x = (p-1)%p。
因此可以得到，原根的个数是p-1的乘法群中元素的个数，也就是欧拉函数(p-1)。

代码如下：

#include
#include
#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;
}