YBTOJ祭—质数与约数

目录

线性筛素数
欧拉筛，老生常谈
个人感觉放这道题的代码不如放板子
//欧拉筛 int prime[maxn]; int factor[maxn]; int Prime(int n) { int p=0; for(int i=2;i<=n;i++) { if(!factor[i]) { prime[p++]=i; factor[i]=i; } for(int j=0;j<p&&prime[j]*i<=n;j++) { factor[prime[j]*i]=prime[j]; if(!(i%prime[j])) break; } } return p; }