1-n中所有数的欧拉phi函数值（小于n且与n互素的整数个数）

int phi[1000005];

void phi_table(int n)
{
    for(int i=2; i<=n; ++i)
        phi[i]=0;
    phi[1]=1;
    for(int i=2; i<=n; ++i)
        if(!phi[i])
            for(int j=i; j<=n; j+=i)
            {
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}