将要学习数论，选择一套题来拓展知识面。机缘巧合之下就理解了埃氏素数筛法，和线性筛法的相似之处，特记下模板以及理解。 简单说一下欧拉函数（来源百度百科）：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。比如：φ（10）=4，那么与他互质的数有哪些呢？ 1，3，7，9。 而求欧拉函数值有一个通式：φ（x）=x*（1-1/x1）（1-1/x2）… 而这些x1，x2等等都是x的质因数，什么是质因数呢？首先要先是质数（素数），其次也要是x的因子，比如x=10，那么x1=2，x2=5，代入得φ（10）=10*(1/2)*(4/5)=4。 但是呢，类似于素数，我们用的时候往往是比较很大很大的范围的数，所以既然素数都有素数筛法打表，那么就会有筛法欧拉函数。 类似于素数筛法，都是找因子的倍数关系的数，素数筛法原理就是2既然是素数，那么2的倍数就不再是素数，统统打死。。。而筛法欧拉函数的原理就根据那个通式来完成的，通式里面，要求x1，x2是质因子，而素数筛法则可以很好的吧所有素数过滤出来，那么每过滤一个素数，那么以它为质因子的数是不是都可以进行一下那个通式的运算？对，这就是原理。 附上代码：
//筛法欧拉函数<by kuangbin> int euler[1000000+10]; void geteuler() { mem(euler,0); euler[1]=1; for(int i=2;i<=1000000;i++) { if(!euler[i]) { for(int j=i;j<=1000000;j+=i) { if(!euler[j]) { euler[j]=j; } euler[j]=euler[j]/i*(i-1); } } } }接着，若只是简单的计算一下单个或少量值得欧拉函数值，就不需要打表啦，所以这个时候，计算单个数的欧拉函数值就应运而出了。
LL euler(LL n) { LL ans=n; for(int i=2;i*i<=n;i++) { if(n%i==0) { ans-=ans/i; while(n%i==0) { n/=i; } } } if(n>1) ans-=ans/n; return ans; }下面解释一下代码。。。看了几十分钟，也是没谁了。。。 首先，我们想一下，怎么去求一个数n的欧拉函数值，答案是求出n的所有质因子，然后套公式。但关键之处有两点，怎么筛选出素数，怎么利用公式求欧拉函数值。 这几行代码，虽然简单，但是却又好多东西。（一点一点解释） 最外层的 for循环和if(n%2)用于判断素数，（可以回忆下判断一个数是不是素数的模板的那一层for循环（for(int i=2;i<=sqrt(n);i++)），但是要记得，这里的i表示的质因子并不能代表全部，因为i（max）=sqrt（n），举个例子，6的话，i表示的质因子只能到2，3的话i循环不到。所以才有了n/=i的特判。 感觉读的人会迷迷糊糊，所以，继续解释， ans-=ans/i;这一行代码变化一下形式就是ans=ans(i-1)/i;似曾相识对吧，上文中有提到过，这就是通式的一部分。我看的时候，在想，既然都已经把所有质因子都代入通式了，为什么还要n去变化，去变小。因为有的一部分质因子在for循环里并没有加入到通式里，如果没加入，n就不会是1，if(n>1) ans-=ans/n;因为任何一个数都可以拆成质因子的乘积，但是，我就想了，难道不在for循环里的质因子只有一个吗？为什么只要一次加入通式就可以了？因为如果有多个质因子没有在for循环里加入通式的话，比如（当然这只是错误的例子）10，假如2，5没有加入通式，那么n的值是10（2*5），那么 ans-=ans/n这个式子分别代入2，5和直接代入10是不一样的，所以我就猜测是不是只剩一个质因子不在for循环里。 那么接着验证我的猜测，重点还是在一句话，所有大于1的正整数都可以拆成质因子的乘积，举个例子，10，sqrt（10）近似为3，所以，剩5不在for循环，若是有质因子不在for循环里，只可能是最大的一个。 还有一点疑惑哦，是为什么n每次除以i，依旧举个例子，n=8，当循环过i==2时，n变成了4，那么若是n能被除成1，说明后面不在有质因子。你觉得呢。 然后呢，就是最后一种代码模板了。。。 线性筛法（同时得到欧拉函数值和素数表）
bool check[1000000+10]; int phi[1000000+10]; int prime[1000000+10]; int tot;//素数的个数 void phi_and_prime() { mem(check,0); phi[1]=1; tot=0; for(int i=2; i<=1000000; i++) { if(!check[i]) { prime[tot++]=i; phi[i]=i-1;//若i是素数，那么φ(i)=i-1。（定理） } for(int j=0; j<tot; j++) { if(i*prime[j]>1000000) break;//只求1000000以内的素数 check[i*prime[j]]=1;//素数的倍数便不是素数 if(i%prime[j]==0)//用于求欧拉函数值 { phi[i*prime[j]]=phi[i]*prime[j]; break; } else { phi[i*prime[j]]=phi[i]*(prime[j]-1); } } } }留下一个自己钻研去吧。。。。0.0
