min_25筛：素数计数

挂两个神仙的博客 https://www.luogu.org/blog/ShadowassIIXVIIIIV/solution-sp34096 https://www.cnblogs.com/cjyyb/p/9185093.html 然后是[luoguP3912素数个数](https://www.luogu.org/problemnew/show/P3912)的31ms代码 ```cpp #include<cstdio> #include<cmath> int prime[1234],v[10010],g1[10010],g2[10010],pcnt; bool isnp[10010]; void sieve(int n) { for(int i=2;i<=n;i++) { if(!isnp[i])prime[pcnt++] = i; for(int j=0,k;j<pcnt&&(k=i*prime[j])<=n;j++) { isnp[k] = 1; if(i%prime[j] == 0)break; } } } void work_g(int n) { int sqr = sqrt(n),end,val,i,j,t1; for(i=1,j=0;i<=sqr;i++)g1[i] = i-1, g2[i] = (v[++j]=n/i)-1; for(j=0;j<pcnt;j++) { end = prime[j]*prime[j]; for(i=1;i<=sqr&&(val=v[i])>=end;i++) t1 = val/prime[j], g2[i] += j-(t1 <= sqr? g1[t1]:g2[n/t1]); for(i=sqr;i>=end;i--)g1[i] += j-g1[i/prime[j]]; } } int main() { int n; scanf("%d",&n); sieve(sqrt(n)); work_g(n); printf("%d",g2[1]); return 0; } ``` （懒