poj1284--原根的性质

关于原根，在百度百科上有着详细的介绍，此题主要考查原根的两个性质

1.只有奇素数才有原根。

2.一个数的原根个数为其欧拉函数的欧拉函数。

综合以上特点，可得到，我们设输入数为n，那么输出结果就为n-1的欧拉函数。（素数的欧拉函数为其自身-1）

#include<iostream>
using namespace std;
int euler(int n){
    int res=1,i;
    for(i=2;i*i<=n;i++){
        if(n%i==0){
            n/=i;
            res*=i-1;
            while(n%i==0){
                n/=i;
                res*=i;
            }
        }
    }
    if(n>1)
    res*=n-1;
    return res;
}
int main(){
    int n;
    while(cin>>n){
        cout<<euler(n-1)<<endl;
    }
    return 0;
}