poj 1284 Primitive Roots 求素數元根數

poj 1284 Primitive Roots 求素數元根數

題意：

給奇素數p,求p有多少原根。

分析：

phi(p-1)，數論有具體證明。

代碼：

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