https://www.luogu.org/problem/show?pid=2158 题目就是求1~n的phi[i]的和 然后*2+1； 这个找规律即可，我们会发现对于点[x,y]如果(x,y)=1那么就可以看见； 这个就是欧拉函数呀； 我们先回顾一下最基本的求1~n的质数的方法；
for (int i=2;i*i<=m;i++) if (s[i]==0) for (int j=2;j<=m/i;j++)s[i*j]=1;//筛法求素数 s[1]=1;//1不是质数（我忘记加了这句话，错了1次）这个时间O(nlog(n)) 反正比O(n)大，而且只能求出质数有哪些； 我们在回顾一下欧拉函数 http://blog.csdn.net/largecub233/article/details/60782683
对于这题，我们要在线性的时间看i求φ（1~n）； φ和five同音（好像），所以写为phi; 方法1
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<cstring> #include<map> #define Ll long long using namespace std; int ans,n,phi[40001];//phi[i]表示1~i中和i互质的数 int main() { scanf("%d",&n); for(int i=2;i<n;i++){ if(!phi[i])//可以知道，当这时，i一定是质数，思路和上面差不多 for(int j=i;j<=n;j+=i){//查看质数i的倍数 if(!phi[j])phi[j]=j;//如果phi[j]一开始是0，先假设1~j都和j互质 //但要注意，这个赋值不可以一开始初始化 //因为我们要靠这个数组来判断i是不是质数 phi[j]=phi[j]/i*(i-1);//先把a割成每段都是i个的，再乘以（i-1）不就把i的倍数给漏掉了吗？ //当然喽，这里phi[j]显然是i的倍数 因为j+=i } ans+=phi[i]; } printf("%d",ans*2+3); }上面那个方法思路就是用每个数x，用x的所有质因数去更新x; 那我们来看欧拉筛 我们要知道3个东西 1.如果x是质数phi[x]=x-1; 这个显然；
2.对于数i，质数j，如果i%j>0那么i,j互质，因为phi是积性函数，phi[i*j]=phi[i]*phi[j] 当然这里phi[j]=j-1; 什么？你问我什么是积性函数？ 如果当i,j互质，f[i*j]=f[i]*[j]那么f就是积性函数； 什么？你问我为什么phi是积性函数； 我也不知道；
3.对于数i，质数j，如果i%j==0; 那么phi[i*j]=phi[i]*j; 我一开始很懵逼； 后来发现这个很傻逼的； 因为i%j==0; 那么i和i*j的质因数会不会变？ 不会啊，因为j本来就是i的质因数啊； 既然这样，对于上面的通式，p1,p2,p3….不会变； 那么是不是就是x多乘了个j 那么phi[i*j]=phi[i]*j; 对吧；
既然我们知道了上面的3点，我们是不是可以用数x的任一一个因数来推出phi[x]; 那我们让每一个数只被其最小的质因数访问，时间是不是变成了O(n)?
从2到n枚举一个i，然后从小到大枚举≤i的质数j。 如果j不是i的因数，那么i*j的最小质因子就是j，并且可以把i*j标记为合数。 否则如果j|i，那么j是i的最小质因子，那么j也是i*j的最小质因子，但j的下一个质数k不是i*k的最小质因子（j才是），那么把i*j标记为合数，并且停止枚举j。可以发现，这个算法可以将所以合数筛去，并且每个合数都只被自己的最小质因子筛去一遍且仅一遍。
对吧？
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<cstring> #include<map> #define Ll long long using namespace std; int ans,n; int phi[40001],pri[40000],tot; bool com[40001];//pri质数简写,com合数简写 void make(int n){ phi[1]=1; for(int i=2;i<=n;i++){ if(!com[i]){phi[i]=i-1; pri[++tot]=i;}//如果是质数 for(int j=1;j<=tot;j++){ if(i*pri[j]>n)break; com[i*pri[j]]=1; if(i%pri[j])phi[i*pri[j]]=phi[i]*phi[pri[j]];else//积性函数 {phi[i*pri[j]]=phi[i]*pri[j];break;}//通式求解 } } } int main() { scanf("%d",&n); make(n); for(int i=2;i<n;i++)ans+=phi[i]; printf("%d",ans*2+3); }当我兴奋地交了欧拉时 ？？？？ 为什么欧拉筛慢？？？？？ 我用ctime记录了时间 n=40000; 欧拉 0ms 非欧拉 0ms
n=1000000 欧拉 16ms 非欧拉 46ms
n=1e8 欧拉 2500ms 非欧拉 7866ms 貌似大数据欧拉才有优势；
然后我发现等我写完博客我就不用做题，可以直接睡觉了； 呵呵；
那么欧拉怎么筛质数呢？ 是不是只要枚举到sqrt(n)就好了呢？ 不是的
#include<iostream> #include<cstdio> #define ll long long using namespace std; const int M=1e2; int q[M+5],tot; bool com[M+5]; void findcom(){ com[1]=1; for(int i=2;i<=M;i++){ if(!com[i]){q[++tot]=i;} for(int j=1;j<=tot;j++){ if(i*q[j]>M)break;//一定要加 com[i*q[j]]=1; if(i%q[j]==0)break; } } } int main(){ findcom(); for(int i=1;i<=tot;i++)cout<<q[i]<<endl; }不难看出，虽然100的最小质因数是2，但只有i枚举到50的时候100才会被50*2跟新；
然后最近自己又打了一次 首先那个com数组可以省略用phi代替判断 另外我们肉眼对拍自己打没打错，要输出phi[1~3000]的和，不要仅仅输出phi[1~20]的值,有些小误差看不出来的
