题解 P3912 【素数个数】

· · 题解

没人会Java吗？

不可能，肯定有。那我就发一篇Java版本的题解吧。

我们可以用普通的素数筛法来做这一道题。比如说如果i是素数，那么处i本身以外所有i的倍数都不是素数。所以代码应该这样：

for(int j=i*i;j<=n;j+=i) bz[i]=true;

这里解释一下为什么是i × i，很简单，因为在筛前面的数的时候就已经把小于 i 的所有质因数筛掉了，所以这里只用从i × i开始筛。

既然这里是从i × i，为了防止RE（这是用编者的正确率换来的）那么最外围的循环也该变一下了。筛素数过程的代码如下：

bz=new boolean[n+10];
for(i=2;i*i<=n;i++)
{
    if(!bz[i])
    {
        ans++;
        for(int j=i*i;j<=n;j+=i) bz[j]=true;
    }
}
for(;i<=n;i++)if(!bz[i])ans++;

完整代码：

import java.util.*;

public class Main
{
    public static void main(String args[])
    {
        boolean[] bz;
        int n,ans=0,i;
        Scanner in=new Scanner(System.in);
        n=in.nextInt();
        bz=new boolean[n+10];
        for(i=2;i*i<=n;i++)
        {
            if(!bz[i])
            {
                ans++;
                for(int j=i*i;j<=n;j+=i) bz[j]=true;
            }
        }
        for(;i<=n;i++)if(!bz[i])ans++;
        System.out.println(ans);
    }
}

完美结束