@command_block 不过后期公式比较长，或考虑将字体放大？\large

（蒟蒻光速逃）

现在大家太热情了队列太长了 [呲牙][呲牙][呲牙]

1888回复

1888回复

学术版第一高楼？

感觉现在的日报越来越短了。。。

社长好厉害; 崇拜你，崇拜你；

@huanghaox1212 n=3e8时，可测得：

p[0]=p[1]=false;
for(int i=2;i*i<=n;++i)
    if(p[i])
        for(int j=i*i;j<=n;j+=i)p[j]=false;

时间为：3216ms,3215ms,3203ms

p[0]=p[1]=false;
for(int j=4;j<=n;j+=2)p[j]=false;
for(int i=3;i*i<=n;i+=2)
    if(p[i])
        for(int j=i*i;j<=n;j+=i)p[j]=false;

时间为：3213ms,3209ms,3204ms

p[0]=p[1]=false;
for(int j=4;j<=n;j+=2)p[j]=false;
for(int j=9;j<=n;j+=3)p[j]=false;
int k=sqrt(n)-1;
for(int i=6;i<=k;i+=6){
    int u=i-1,v=i+1;
    if(p[u])
        for(int j=u*u;j<=n;j+=u)p[j]=false;
    if(p[v])
        for(int j=v*v;j<=n;j+=v)p[j]=false;
}

时间为：3206ms,3216ms,3222ms

测评环境是Red Hat Enterprise Linux Server 7.2，Intel® Xeon(R) CPU E5-2620 v4 @ 2.10GHz × 32，64位，UOJ评测系统

快把这些全删了，看着丢人（不如讲讲如何$O(\sqrt{n})$空间，或者 primesieve.org 呢

跟你说了你是在改良无关紧要的$O(\sqrt{n})$

性质4处没说明p为素数；

你就说裸埃筛复杂度是$O(n \log \log n)$有什么不好啊，非要假装分析一下，又分析得乱七八糟；就算你打了前$O(\sqrt{n})$的表，复杂度也不会降低

你这些小小的优化根本就没法改良时间，瓶颈绝对在后面的for(int j=i*i;j<=n;j+=i)p[j]=false;，内存访问巨慢