定理：假如一个数x有原根，则元根的个数为phi(phi(x)),phi（x）为小于x且与x互质的正整数个数。
#include <iostream>
#include <cmath>
using namespace std;
int p;
int f(int x){
int ans=x;
int m=sqrt(x+0.5);
for(int i=2;i<=m;i++)if(x%i==0){
ans=ans/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)ans=ans/x*(x-1);
return ans;
}
int main()
{
while(cin>>p)cout<<f(f(p))<<endl;
return 0;
}
原文：http://www.cnblogs.com/wshh/p/3961565.html