题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=102

题目大意：

     求不大于N且与N互质的数的个数。

解题思路：

      刚开始就想到暴力法，枚举每个数看看是不是gcd(n,i)==1。

      后来想到了欧拉函数，这不就是典型的欧拉函数题，先分解素数然后求欧拉函数。

      欧拉函数法用的时间是暴力法的一半。

解题代码：

#include<iostream>
using namespace std;
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main(){
	int n;
	while(cin>>n){
		int sum=0;
		for(int i=1;i<=n;i++){
			if(gcd(n,i)==1)
				sum++;
		}
		cout<<sum<<endl;
	}
}

#include<iostream>
#include<cstring>
using namespace std;
#define Max 10000
bool isprime[Max+10];
int  prime[Max+10];
int  countp;
void mkprime(int n){
	countp=1;
	memset(isprime,true,Max+10);
	prime[0]=2;
	for(int i=3;i<=n;i+=2){
		if(isprime[i]==true){
			prime[countp++]=i;
			for(int j=1;i*j<=n;j++)
				isprime[i*j]=false;
		}
	}
}
int eular(int n){
	for(int i=0;prime[i]<=n&&i<countp;i++)
		if(n%prime[i]==0){
			n/=prime[i];
			n*=prime[i]-1;
		}
	return n;
}
int main(){
	int n;
	while(cin>>n){
		mkprime(n);
		if(n==1)
			cout<<1<<endl;
		else
			cout<<eular(n)<<endl;
	}
}

 扩展知识：

http://en.wikipedia.org/wiki/Euler%27s_totient_function

http://linuxsir.org/bbs/showthread.php?t=278294