poj 1284 : Primitive Roots

题目链接

题意：求给定的奇素数的原根个数

定理：如果p有原根，则它恰有φ(φ(p))个不同的原根，p为素数，当然φ(p)=p-1,因此就有φ(p-1)个原根

#include<cstdio>
#include<cstring>

const int maxn=1e6+7;
int phi[maxn+5];
void init()
{
    memset(phi,0,sizeof(phi));  //初始化为0
    phi[1]=1;
    for(int i=2; i<=maxn; i++)
    {
        if(!phi[i])     //当i是质数时
            for(int j=i; j<=maxn; j+=i)      //筛选所有因子为i的数
            {
                if(!phi[j]) phi[j]=j;       //若未赋值过，先初始化
                phi[j]=phi[j]/i*(i-1);      //i是质因数(1-1/i)=(i-1)/i，先除再乘是为了防止越界。
            }
    }
}

int main()
{
    init();
    int n;
    while(~scanf("%d",&n))
        printf("%d
",phi[n-1]);
}