最近学数论,我是真的绝望,欧拉筛法也只能靠背代码勉强凑合凑合,但在我社CSQ大佬的帮助下,我理解到了其中神奇的奥妙
欧拉筛法是一种可以筛出质数,欧拉函数,约数个数和约数和的筛法 那么我们就对这些问题逐一进行讲解
在这之前,我们先说几个东西:
1、每一个大于等于2的正整数nn,都有n=p_1^{w_1}p_2^{w_2}…p_m^{w_m}n=p1w1p2w2…pmwm(p_1p1到p_mpm按升序排列)
2、正整数nn的欧拉函数phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_m})=p_1^{w_1-1}(p_1-1)*p_2^{w_2-1}(p_2-1)*…*p_m^{w_m-1}(p_m-1)phi(n)=n(1−p11)(1−p21)…(1−pm1)=p1w1−1(p1−1)∗p2w2−1(p2−1)∗…∗pmwm−1(pm−1)
3、正整数nn的约数个数d(n)=(1+w_1)(1+w_2)…(1+w_m)d(n)=(1+w1)(1+w2)…(1+wm)
4、正整数nn的约数和s(n)=(1+p_1+p_1^2+…+p_1^{w_1})(1+p_2+p_2^2+…+p_2^{w_2})……(1+p_m+p_m^2+…+p_m^{w_m})s(n)=(1+p1+p12+…+p1w1)(1+p2+p22+…+p2w2)……(1+pm+pm2+…+pmwm)
inline void sieve(int x) { for(reg int i = 2;i <= x;i ++) { if(! vis[i]) prim[++ len] = i; for(reg int j = 1;j <= len && i * prim[j] <= x;j ++) { vis[i * prim[j]] = 1; if(i % prim[j] == 0) break; } } }
inline void sieve(int x) { phi[1] = 1; for(reg int i = 2;i <= x;i ++) { if(! vis[i]) { prim[++ len] = i; phi[i] = i - 1; //因为欧拉函数代表小于这个数的且与这个数互质的数的个数,所以质数的欧拉函数为它本身减1 } for(reg int j = 1;j <= len && i * prim[j] <= x;j ++) { vis[i * prim[j]] = 1; if(i % prim[j] == 0) { phi[i * prim[j]] = phi[i] * prim[j]; break; } phi[i * prim[j]] = phi[i] * (prim[j] - 1); } } }
inline void sieve(int x) { for(reg int i = 2;i <= x;i ++) { if(! vis[i]) { prim[++ len] = i; d[i] = 2; //质数的约数只有1和它本身 sum[i] = 1; } for(reg int j = 1;j <= len && i * prim[j] <= x;j ++) { vis[i * prim[j]] = 1; if(i % prim[j] == 0) { sum[i * prim[j]] = sum[i] + 1; d[i * prim[j]] = d[i] / (sum[i] + 1) * (sum[i] + 2); break; } sum[i * prim[j]] = 1; d[i * prim[j]] = d[i] * 2; } } }
inline void sieve(int x) { for(reg int i = 2;i <= x;i ++) { if(! vis[i]) { prim[++ len] = i; psum[i] = s[i] = i + 1; } for(reg int j = 1;j <= len && i * prim[j] <= x;j ++) { vis[i * prim[j]] = 1; if(i % prim[j] == 0) { psum[i * prim[j]] = psum[i] * prim[j] + 1; s[i * prim[j]] = s[i] / psum[i] * psum[i * prim[j]] break; } psum[i * prim[j]] = prim[j] + 1; s[i * prim[j]] = s[i] * psum[i * prim[j]]; } } }