题解 P3912 【素数个数】

mylsl · 2018-03-01 20:24:22 · 题解

线性筛素数

prime[x]表示x是不是素数

从2开始枚举，把2的所有倍数都标记成不是素数； 枚举3，把3的所有倍数都标记成不是素数；

......

以此类推，剩下的数就是素数，因为它们不是任何素数的倍数

查询素数个数

法1：暴力数：TLE

for(int i=2;i<=n;i++)
        cnt+=prime[i];

法2：总共有n个数，减去不是素数的即可：TLE

for(int i=2;i<=n;i++)
{
    if(!prime[i]){cnt--;continue;}
    for(int j=2;j*i<=n;j++)
        prime[i*j]=false;
    }

法3：6=2x3=3x2 通过控制i<=sqrt(n),避免重复计算：AC

for(int i=2;i*i<=n;i++)
{
    if(!prime[i])continue;
    for(int j=2;j*i<=n;j++)
        if(prime[i*j])prime[i*j]=false,cnt--;
    }

20行AC代码

#include <cstdio>
#include <memory.h>
using namespace std;
bool prime[100000001];
int n,cnt;
int main()
{
    memset(prime,true,sizeof(prime));
    prime[1]=false;
    scanf("%d",&n);
    cnt=n-1;//1不是质数
    for(int i=2;i*i<=n;i++)
    {
        if(!prime[i])continue;
        for(int j=2;j*i<=n;j++)
            if(prime[i*j])prime[i*j]=false,cnt--;
    }
    printf("%d\n",cnt);
    return 0;
}