线性筛

for(int i=2;i<=n;++i) {if(!vis[i]) pri[++cnt]=i;for(int j=1;j<=cnt&&i*pri[j]<=n;++j) {vis[i*pri[j]]=1;if(i%pri[j]==0) break;}
}

只会被最小的素数筛掉。
$n=p_1^{k_1}\ast p_2^{k_2}\dots \dots p_x^{k_x}$
枚举的$i$为$\frac{x}{p_1}$，x就是被筛掉的值。
因为找到的素数都是从小到大的，所以从小到大枚举就好了。
当$i\%pri[j]==0$ 就是说枚举到了$i$的最小质因子。这之后的素数因为都比他大，所以都不合格，就break了。
之前的$pri[j]$都会比这个pri[j]小都是可以的，每个pri[j]都是i*pri[j]的最小质因子。
可以很方便的求积性函数，只需要毒瘤的简单的分类讨论就好了。
对于下方的东西，请移步cnblogs

求莫比乌斯函数

求欧拉函数

约数个数

约数和