Sgu/102

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=10000;
bool isprime[MAXN+10];
int primelist[MAXN+10];
int cntpri;
void make_prime()
{
     int i,j;
     memset(isprime,true,MAXN+10);
     isprime[2]=isprime[3]=true;
     primelist[0]=2;
     cntpri=1;
     for(i=3;i<MAXN+1;i+=2)
     {
          if(isprime[i])
          {
            primelist[cntpri++]=i;
            for(j=2;j*i<MAXN+1;j++)
              isprime[i*j]=false;                 
          }
     }
#ifdef LOCAL
     for(i=0;i<100;i++)
       cout<<primelist[i]<<endl;
#endif
     return;
}
int euler(int n)
{
    int i;
    for(i=0;primelist[i]<=n && i<cntpri ;i++) //&& i<cntpri
    {
        if(n%primelist[i]==0)
        {
            n/=primelist[i];
            n*=(primelist[i]-1);
        }                                    
    }
    return n;
}
int main()
{
      make_prime();
      int n;
      while(cin>>n)
      {
          if(n==1)
            cout<<"1"<<endl;
          else
            cout<<euler(n)<<endl;         
      }
      return 0;
}

#include<stdio.h>
int gcd(int x, int y) {return x%y==0?y:gcd(y,x%y);}
int main()
{
	int n,i,ans=0;
	scanf("%d",&n);
	for(i=1; i<=n; i++) 
	 if(gcd(i,n)==1) ans++;
	printf("%d\n",ans);
	return 0;
}

被1的情况坑死了Rapheal