poj 1284 Primitive Roots 求素数元根数

题意：

给奇素数p,求p有多少原根。

分析：

phi(p-1)，数论有具体证明。

代码：

//poj 1284
#include <iostream>
using namespace std;int main()
{int n;while(scanf("%d",&n)==1){--n;int ans=n;for(int i=2;i*i<=n;++i)if(n%i==0){ans-=ans/i;while(n%i==0)n/=i;}if(n!=1)ans-=ans/n;printf("%d\n",ans);}return 0;	
}