1.线性筛 素数 欧拉 莫比乌斯
欧拉筛：
#include <stdio.h> #include <algorithm> #include <cstring> using namespace std; const int maxn=200000; int pri[maxn],phi[maxn],vis[maxn],n; int cnt; void pre() { phi[1]=1;//初始话请注意 for(int i = 2;i <= n; i++ ) { if(!vis[i]) { pri[cnt++] = i; phi[i] = i - 1; } for(int j = 0; j < cnt , i * pri[j] <= n; j++)//cnt++ 对应过来的就是要<cnt.否则就会越界访问 { vis[i * pri[j]] = 1;//先做标记 if(i % pri[j] ) { phi[i * pri[j]] = phi[i] * (pri[j]-1); } else { phi[i * pri[j]] = phi[i] * pri[j]; break;//i已经被更小的质因数晒过了，所以不需要继续，直接break } } } } int main() { scanf("%d",&n); pre(); for(int i = 0;i < cnt; i++ ) printf("%d ", pri[i]);printf("\n"); for(int i = 1;i <= n; i++ ) printf("%d ", phi[i]); return 0; }
莫比乌斯筛
#include <stdio.h> #include <algorithm> #include <cstring> using namespace std; const int maxn=200000; int prime[maxn],vis[maxn],mob[maxn],cnt; int n; void pre() { mob[1]=1; for(int i = 2; i <= n; i++) { if(!vis[i]) { mob[i] = -1; prime[cnt++] = i; } for(int j = 0; j < cnt, i * prime[j] <= n; j++) { vis[i * prime[j]] = 1; mob[i * prime[j]] = i % prime[j] ? - mob[i] : 0; if(i % prime[j] == 0) break; } } } int main() { scanf("%d", &n); pre(); for(int i = 1; i <= n; i++) printf("%d ", mob[i]); return 0; }
注意几个重要的性质：1.质数一定为-1，如果i这个数可以被p整除，那么他的i*p一定为-mob[i]（至少增添了一对平方因子，相反），否则不整除，那么这里就一定是0了；
求约数个数
#include <stdio.h> #include <algorithm> using namespace std; const int maxn=200000; int n,prime[maxn],minn[maxn],d[maxn],vis[maxn]; int cnt; void pre() { d[1]=1; for(int i = 2; i <= n; i++ )//线性的筛法都是基于素数筛，所以说一定是从2来开始的，1一定是特殊判断 { if(!vis[i]) { prime[cnt++] = i;//cnt++和++cnt一定要区分 minn[i] = 1; d[i] = 2; } for(int j = 0; j < cnt, i * prime[j] <= n; j++) { vis[i * prime [j]]=1; if(i % prime[j] == 0) { d[i * prime[j]] = d[i] / (minn[i] + 1) * (minn[i] + 2); minn[i * prime[j]] = minn[i] + 1; break; } else { d[i * prime[j]] = d[i] * 2; minn[i * prime[j]] = 1; } } } } int main() { scanf("%d",&n); pre(); for(int i = 1; i <= n; i++) printf("%d ", d[i]); }
理论证明如下
约数个数 算术基本定理中，根据拆分后的素因子的指数，我们可以求出每个 N 的约数的个数。 根据这个式子，我们可以用线性筛去筛出当前 N 的约数个数。 筛的过程中，我们需要保存下最小素因子的个数。 下面证明中 d(i) 表示 i 的约数个数 num[i] 表示 i 的最小素因子的个数 prim[i] 表示 第 i 个素数 ① 当前数是素数 这种情况我们很容易得到，当前的 d(N) = (1+1) = 2， 因为素数只有一个素因子(就是它本身)，并且指数为 1 。 而最小素因子个数 num[N] = 1 ② i%prim[j] !=0 这种情况，我们可以知道 i 当中，并不包含 prim[j] 这个素因子，然而，i*prim[j] 中， 包含了一个 prim[j] 我们可以从前面得到 i 的所有约数个数 然后在补上 当前多了 素因子 prim[j] 的个数 所以最后 d(i*prim[j]) = d(i)*d(prim[j]) 而且由于 当前的 prim[j] 必然是 i*prim[j] 的最小素因子 (因为从小到大枚举啊!)， 我们要记录下这个最小素因子的个数 所以保存一个个数 num[i*prim[j]] = 1 ③ i%prim[j]==0 这种情况， i 中必然包含了至少 1 个 prim[j] ，而且 prim[j] 也必定是 i 的最小素因子，因为每次枚举都是从小的素数开始枚举。 而 i*prim[j] 比起 i 则是多了一个最小素因子个数，即 那么 i*prim[j] 的约数个数 应该是 之后，我们就要用到我们之前记录下的最小素因子个数了，因为我们可以知道 i 的最小素因子个数 为 num[i] ，而 d(i) 中 已经包含了 这时我们 我们可以除去第一项 然后乘以 ，就可以得到 d(i*prim[j]) 的约数个数了。 d(i*prim[j]) = d(i) / (num[i]+1) * (num[i]+2) 当前 num[i*prim[j]] = num[i]+1 ，继续保存下当前最小素因子个数。 根据这样，我们就能用线性筛打表出 1 到 N 的数的约数个数。
求约数和（其实和求约数的个数是一个道理的东西）
#include <cstdio> #include <algorithm> using namespace std; const int maxn=200000; int prime[maxn],d[maxn],sp[maxn],vis[maxn]; int n,cnt; void pre() { d[1]=1; for(int i = 2;i <= n; i++) { if(!vis[i]) { prime[cnt++] = i; sp[i] = i + 1; d[i] = i + 1; } for(int j = 0; j < cnt, i * prime[j] <= n; j++) { vis[i * prime[j]] = 1;//ÿ´Î½øÀ´Ïȱê¼Ç if(i % prime[j] == 0) { sp[i * prime[j]] = sp[i] * prime[j] + 1; d[i * prime[j]] = d[i] / sp[i] * sp[i * prime[j]]; break; } d[i * prime[j]] = d[i] * d[prime[j]];// sp[i * prime[j]] = prime[j] + 1; } } } int main() { scanf("%d", &n); pre(); for(int i = 1; i <= n; i++ ) printf("%d ", d[i]); return 0; }
原文：https://www.cnblogs.com/ILHYJ/p/13579648.html
