素数筛选
标签: 机试攻略 - 高分篇
学习人数: 16.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 素数


登录后开始许愿

暂无评论,来抢沙发