埃式筛

题目

传说有一个宝藏在某地，小码哥碰巧拿到了关于这个宝藏的地图，为了快点拿到宝藏于是他选择走直线，起点标记为 1，宝藏的位置标记为 n ，路途中凡是坐标为质数的地方都存在着怪物，但这些怪物如果获得了一点食物就会放行小码哥，请帮助小码哥计算出会遇到多少只怪物，以方便他在出发前准备好充足的食物。

格式

输入格式：

一行一个正整数n表示宝藏的位置

输出格式：

一行一个整数，表示小码哥遇到的怪物数量

样例 1

输入：

100

输出：

25

备注

其中：$0<n≤1e5$。

思路

打表数据范围内所有质数，依次判断和宝藏所在位置的前后。

需要注意宝藏所在地如果为质数也要计入。

---

在打表时使用了朴素算法，如果数据范围较大，可以改用埃氏筛，其用于快速求特定范围n以内的质数个数，思路如下：

• 从2开始枚举，标记每个未被标记的数的倍数为合数
• 遍历到m(m为使得m*m>=n成立的最小值）即可，此时未被标记的数就是1-n范围内的质数。

因为每个被遍历到的未被标记数一定是质数，因此不用再单独判断该数是否为合数。

Code

提交代码

#include<bits/stdc++.h> 
using namespace std;

int P[]={};   //打表的质数，此处略去。
int n=9592;
int main( )
{
    int num=0,res=0; 
    cin>>num;
    for(int i=0;i<9592;i++){
        if(P[i]<=num)res++;
        else break;
    }
    cout<<res;
    return 0;
}

打表

#include<iostream>
using namespace std;

int n = 1e5 ;
bool isP = false;

int index = 2;

int main() {
    for (int i = 4;i <= n;i++) {
        isP = true;
        for (int j = 2;j * j <= i;j++) {
            if (i % j == 0) {
                isP = false;
                break;
            }
        }
        if (isP) {
            cout << i << ",";
            index++;
        }
    }

    cout << endl << index;
    return 0;
}

基于埃氏筛的质数打表

#include<iostream>
using namespace std;

//用埃氏筛实现1e5范围内的质数打表

const int N = 1e5+1;       //注意边界处理
bool isComp[N] = { false };

int main() {
    for (int i = 2;i*i < N;i++) {
        if (isComp[i] == false) {
            for (int j = i;i * j < N;j++) {
                isComp[i * j] = true;    //标记合数
            }
        }
    }

    //打印
    int sum = 0;
    for (int i = 2;i < N;i++) {
        if (isComp[i] == false) {
            cout << i << ",";
            sum++;
        }
    }
    cout << endl << sum << endl;
    return 0;
}