1136欧拉函数

//超时版本
#include<iostream>
#include<cstring>
#include<cmath> 
#include<algorithm>
using namespace std;
//求一个数的所有质因子
const int maxn=100;//必须是const 
int a[maxn];
int cnt=0;
int d=0;
bool isprime[maxn];
int prime[maxn];
int m;
int zhi[maxn];
int zyinzi[100];
void yinzi(int n)//求出一个数的因子 
{
	for(int i=1;i<=n;i++)
	{
		if(n%i==0)
		{
			a[cnt++]=i;
		}
	}
 } 
 void getprime(int n)//素数 
 {
 	for(int i=1;i<=n;i++)
 	{
 		isprime[i]=true;
	 }
	 for(int i=2;i<=n;i++)
	 {
	 	if(!isprime[i])
	 	{
	 		continue;
		 }
		 prime[d++]=i;
		 for(int j=2*i;j<=n;j+=i)
		 {
		 	isprime[j]=false;
		 }
	 }	 
 }
 int main()
 {
 	int count=0;
 	cin>>m;
 	yinzi(m);
 	getprime(m);
// 	for(int i=0;i<d;i++)
// 	{
// 		cout<<prime[i]<<endl;
//	 }
//	 for(int i=0;i<cnt;i++)
//	 {
//	 	cout<<a[i]<<endl;
//	 }
//	 
	 	for(int i=0;i<cnt;i++)
 	{
 		for(int j=0;j<d;j++)
 		{
 			if(a[i]==prime[j])//找出他的质因子 
 			{ 
 			    //cout<<a[i]<<endl;
 			    zhi[count++]=a[i];
 			    //cout<<zyinzi[count--]<<endl;
 				break; 
 			} 
		 }
	 }
	 for(int i=0;i<count;i++)
	 {
	 	m=(m/zhi[i])*(zhi[i]-1);
	 }
	 cout<<m<<endl;
 }
 
 
 //加强版
 #include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main() {
    int n ;
    while(~scanf("%d",&n)){
        int ans = n;
        int tmp = n ;
        int m = sqrt(n+0.5) ;
        for( int i = 2 ; i <= m ;++i) {
            if(n==1)break;
            if(n%i==0){
                ans = ans/i*(i-1) ;
                while((n%i)==0) n/=i ;
            }
        }
        if(n!=1)ans = ans/n*(n-1) ; // 至多有一个大素因子（可能为本身）
        printf("%d\n",ans) ;
    }
    return 0 ;
}