正文

洛谷 P3912 素数个数

IP云
IP云V管理员/0 阅读
11/30
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

P3912 素数个数

题目描述

求1,2,\cdots,N1,2,⋯,N 中素数的个数。

输入输出格式

输入格式：

1 个整数NN。

输出格式：

1 个整数，表示素数的个数。

输入输出样例
输入样例#1： 复制 
10
输出样例#1： 复制 
4

说明

• 对于40% 的数据，1 \le N \le 10^61≤N≤106；

• 对于80% 的数据，1 \le N \le 10^71≤N≤107；

• 对于100% 的数据，1 \le N \le 10^81≤N≤108。

思路：RE，线性筛一边就可以做出来。bool只占一个字节，所以不会MLE。 

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,tot;

int prime[];

bool yes[];

void shai(){

    memset(yes,true,sizeof(yes));

    yes[]=false;

    for(int i=;i<=n;i++){

        if(yes[i])    prime[++tot]=i;

        for(int j=;i*prime[j]<=n;j++){

            yes[i*prime[j]]=false;

            if(i%prime[j]==)    break;

        }

    }

}

int main(){

    scanf("%d",&n);

    shai();

    cout<<tot;

}

把上面的代码多开一个0 就可以AC了。 

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int n,tot;

int prime[];

bool yes[];

void shai(){

    memset(yes,true,sizeof(yes));

    yes[]=false;

    for(int i=;i<=n;i++){

        if(yes[i])    prime[++tot]=i;

        for(int j=;i*prime[j]<=n;j++){

            yes[i*prime[j]]=false;

            if(i%prime[j]==)    break;

        }

    }

}

int main(){

    scanf("%d",&n);

    shai();

    cout<<tot;

}

当然听说大佬用了一种叫Meissel Lehmer Algorithm的算法跑的飕飕的。对于我一个蒟蒻来说，这个算法太高级了，诸君还是自行学习吧。我在这里就不粘代码了。

相关阅读

目录[+]