[关键字]：数学 数论 公约数 欧拉函数
[题目大意]：给出一个整数n，求出<=n的与n互质的数的个数。
//================================================================================================
[分析]：欧拉函数就是求出小于等于x的互质的数有几个。
公式：φ(x)=x*(1-1/p1)*(1-1/p2)*......*(1-1/pn)，其中pi是x的质因数。
性质：1、φ(x)=x-1，其中x为指数
2、φ(xy)=φ(x)*φ(y)，其中gcd(x,y)=1
根据性质可以找出在O(n)复杂度内的算法：利用线性筛素法。
每筛到一个素数x：
1、φ(x)=x-1，
并在每次利用现有素数筛时：
2、如果i%x==0 φ(i*x)=φ(i)*x，
3、否则φ(i*x)=φ(i)*(x-1)
[代码]：
View Code #include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<algorithm>using namespace std;const int MAXN=50000;int n,sum;bool b[MAXN];int E[MAXN],p[MAXN];int main(){ scanf("%d",&n); memset(b,0,sizeof(b));for (int i=2;i<=n;++i) {if (!b[i]) { p[++sum]=i; E[i]=i-1; }for (int j=1;(j<=sum && i*p[j]<=n);++j) { b[i*p[j]]=1;if ((i%p[j])==0) { E[i*p[j]]=E[i]*p[j];break; }else E[i*p[j]]=E[i]*(p[j]-1); } } E[1]=1; printf("%d\n",E[n]); system("pause");return 0;}转载于:https://www.cnblogs.com/procedure2012/archive/2012/03/22/2412086.html
相关资源：垃圾分类数据集及代码