素数筛选 - N诺考研

标签: 机试攻略 - 高分篇

学习人数: 19.5k

有的时候，题目要求我们筛选出一段区间内的素数，我们就需要掌握一种素数筛选的方法。

如果用上一节素数判定的方法去判定每一个数是不是素数的话。
复杂度是O(n*sqrt(n))，大概能处理到10000以内的数。

如果题目要求的范围更大，那么我们就需要一种更为高效的筛选法。
掌握下面这一种线性复杂度的筛选方法就足够我们应对任何情况。

// 线性素数筛选  prime[0]存的是素数的个数  
const int maxn = 1000000 + 5;  
int prime[maxn];  
void getPrime() {  
    memset(prime, 0, sizeof(prime));  
    for (int  i = 2; i <= maxn; i++) {  
        if (!prime[i]) prime[++prime[0]] = i;  
        for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {  
            prime[prime[j] * i] = 1;  
            if (i % prime[j] == 0) break;  
        }  
    }  
}

素数判定
题目描述：
给你两个数a、b,现在的问题是要判断这两个数组成的区间内共有多少个素数
输入描述：
多组测试数据。每个测试数据输入两个数a、b。(2<=a,b<=1000)
输出描述：
输出该区间内素数的个数。
输入样例#:
2 4
4 6
输出样例#:
2
1
题目来源：
DreamJudge 1102

题目解析：这道题的数据范围不大，我们可以用挨个暴力判断的方法来解决。我们假设这道题的数据范围很大，使用素数筛选的方法来解决这个问题。

参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
// 线性素数筛选  prime[0]存的是素数的个数  
const int maxn = 1000000 + 5;  
int prime[maxn];  
void getPrime() {  
    memset(prime, 0, sizeof(prime));  
    for (int  i = 2; i <= maxn; i++) {  
        if (!prime[i]) prime[++prime[0]] = i;  
        for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) {  
            prime[prime[j] * i] = 1;  
            if (i % prime[j] == 0) break;  
        }  
    }  
}  
int main() {  
    getPrime();//先进行素数筛选预处理  
    int a, b;  
    while (scanf("...

登录查看完整内容

课后作业

练习题目

DreamJudge 1375 素数

登录后开始许愿

2 条上岸许愿

Lepain

2026年3月14日 20:59

#include<bits/stdc++.h>
using namespace std;
const int N=1000000+10;
int prime[N],cnt;
class Solution{
public:
   void get_prime(int n){
       bool not_prime[N];
       for(int i=2;i<=n;i++){
           if(not_prime[i]==false){
               prime[cnt]=i;
               cnt++;
           }
           for(int j=0;prime[j]<=n/i;j++){
               not_prime[prime[j]*i]=true;
               if(i%prime[j]==0) break;
           }
       }
   }
};
int main(){
   cout<<"输入两个数：";
   int x,y;
   cin>>x>>y;
   Solution sol;
   sol.get_prime(y);
   int i=0;
   while(true){
       if(prime[i]>=x) break;
       i++;
   }
   return cnt-i;
}

Lepain 回复 Lepain：假设x比y小

2026年3月14日 21:00

liux662

2026年1月21日 09:42

maxn = 1000000 + 5但是for (int i = 2; i <= maxn; i++)，for循环里面不会出问题吗