ARTICLE · 1296364

信息学奥赛实战真题:求质数/素数筛法

发布时间：2026-11-02 15:34:45 最近访问：2026-11-02 15:34:46

信息学奥赛实战真题:求质数/素数筛法

Question

素数又称为质数，指在一个大于1的自然数中，除了1和此整数自身外，无法被其他自然数整除的数。比1大，但不是素数的称为合数。0和1既不是素数也不是合数。

求闭区间 [ X , Y ] 内素数的个数。

输入格式

两个整数 X 和 Y( 1 ≤ X,Y ≤ 1.1×10⁶)。

输出格式

输出一个整数，表示闭区间 [ X , Y ] 内素数的个数。

输入输出样例

输入——

1 100

输出——

方法1，试除/法暴力筛——

Solution A in C++

#include<iostream>#include<algorithm>using namespace std;int X=0,Y=0,ans=0;boolisPrime(int k){//bool判断素数，false表示不是质数，true表示是质数    if ( k== 1) return false; //特判，1不是素数    else if (k == 2) return true; // 特判，2是素数，  //for (int i = 2; i<= k; i++) {//方便初学者理解，但是时间复杂度过高的写法    for (int i = 2; i * i <= k; i++) {//能除尽，说明不是素数        if (k % i == 0) return false;    }    return true;}intmain(){    cin>>X>>Y;    int s=min(X,Y),e=max(X,Y);//s:起点 e:终点    for(int i=s;i<=e;i++)        if(isPrime(i))            ans++;    cout<<ans<<endl;    return 0;}

方法2， 6k±1法——

Solution B in C++

#include<iostream>#include<algorithm>using namespace std;int X=0,Y=0,ans=0;boolisPrime(int k){//bool判断素数，false表示不是质数，true表示是质数    if ( k== 1) return false; //特判，1不是素数    else if (k <= 3) return true;  // 2 和 3 是质数    if (k % 2 == 0 || k % 3 == 0) return false; //能被 2 和 3 整除的都不是质数    for (int i = 5; i * i <= k; i += 6) {        if (k % i == 0 || k % (i + 2) == 0)//6k-1||6k+1            return false;    }    return true;}intmain(){    cin>>X>>Y;    int s=min(X,Y),e=max(X,Y);//s:起点 e:终点    for(int i=s;i<=e;i++)        if(isPrime(i))            ans++;    cout<<ans<<endl;    return 0;}

方法3，埃氏筛——

埃氏筛法的基本思想：从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。

Solution C in C++

#include<iostream>#include<cstring>//memset的头文件using namespace std;const int MAX = 1100000;bool is_prime[MAX + 1];   // is_prime[i] = true 表示 i 是素数int prefix[MAX + 1];      // 前缀和数组，prefix[i] = 1~i 中的素数个数voideratosthenes_sieve(){    // 初始化：假设所有数都是素数    memset(is_prime, true, sizeof(is_prime));    is_prime[0] = is_prime[1] = false;  // 0 和 1 不是素数    for (int i = 2; i * i <= MAX; i++) {        if (is_prime[i]) {            // 如果 i 是素数，标记它的所有倍数为合数            for (int j = i * i; j <= MAX; j += i) {                is_prime[j] = false;            }        }    }    // 构建前缀和数组    prefix[0] = 0;    for (int i = 1; i <= MAX; i++) {        prefix[i] = prefix[i - 1] + (is_prime[i] ? 1 : 0);    }}intmain(){    eratosthenes_sieve();    int X, Y;    cin >> X >> Y;    // 注意：X 可能大于 Y，需要交换    if (X > Y) swap(X, Y);    int ans = 0;    //int ans = prefix[Y] - prefix[X - 1];//前缀和求解，与下面三行二选一    for (int i = X; i <= Y; i++) {        if(is_prime[i]) ans++;    }    cout << ans << endl;    return 0;}

方法4，欧拉筛/线性筛——

欧拉筛法的基本思想：在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复的目的。具体来说就是维护一个标记数组 arr 和一个已有素数数组 primes ，然后，我们从2开始遍历所有数 i ，并且——

①把遇到所有未被标记为合数的数 i （埃式筛中从小到大遍历时遇到的一个个质数）存到 primes 里去；

②以 i 为第一个因子，分别以 primes 里每个质数 j 为第二个因子，求积，可以断定 j∗i 必为合数，故标记之；同时，若 mod(i , j)==0 ，说明 j 是 i∗j 的一个质因数，又因为 primes 数组中的元素是递增的， j 是第一个可以除断 i 的，故可断定 j 是 i 的最小质因数，同时也是 i∗j 的最小质因数，那么更进一步也可断定j 之后的质数 j′ 一定不是 i∗j′ 的最小质因数，故结束 primes 的遍历。

Solution D in C++

#include<iostream>#include<cstring>//memser的头文件using namespace std;const int MAX = 1100000;bool is_prime[MAX + 1];//用下标表示的原始整数表int primes[MAX / 10];  // 素数存储数组，估计大小int tot = 0;//素数的个数之和int prefix[MAX + 1];   // 前缀和数组voideuler_sieve(){    memset(is_prime, true, sizeof(is_prime));    is_prime[0] = is_prime[1] = false;    for (int i = 2; i <= MAX; i++) {        if (is_prime[i]) {            primes[tot++] = i;        }        for (int j = 0; j < tot && i * primes[j] <= MAX; j++) {            is_prime[i * primes[j]] = false;            if (i % primes[j] == 0) {                break;// 如果标记过了，直接踹出循环            }        }    }    // 构建前缀和    prefix[0] = 0;    for (int i = 1; i <= MAX; i++) {        prefix[i] = prefix[i - 1] + (is_prime[i] ? 1 : 0);    }}intmain(){    euler_sieve();    int X, Y;    cin >> X >> Y;    // 注意：X 可能大于 Y，需要交换    if (X > Y) swap(X, Y);    int ans = 0;    //int ans = prefix[Y] - prefix[X - 1];//前缀和求解，与下面三行二选一    for (int i = X; i <= Y; i++) {        if(is_prime[i]) ans++;    }    cout << ans << endl;    return 0;}


▍ 声明：本文整理自网络，如有侵权，请联系删除。
本公号刊载此文，是出于合法合理地分享和传播信息，扩大大受众范围，促进学术交流，推动共同进步之目的。公众号持有人郑重声明，本文的发布，将严格遵守相关规定和法律法规，不侵犯任意潜在作者的权益，不改变引用原文（若有）的意图和内容。若有来源标注错误或侵犯了您的合法权益，请随时与我们联系协商，联系（QQ）：993225721，我们将及时更正、删除。文章若有幸得到转载，首先，公众号持有人感谢转载人为读者阅读提供了有价值的信息和知识，希望文章能够在被转载的平台上得到更广泛的传播和交流；其次，转载人应充分考虑到转载动作本身所可能带来的相应的风险和责任，包括但不限于侵犯知识产权、侵犯他人权益等行为所引起的法律责任，确保本文的合法传播和使用。同时，本人也极其愿意在转载过程中尽力配合转载人了解、关注、规避、消除相关的潜在风险。若转载人有相任何关疑虑，同样欢迎随时与我们联系协商，联系（QQ）：993225721。
喜欢您关注我们哦——