算法竞赛入门 — 素数筛


算法竞赛入门 — 素数筛



α. 何谓素数?

素数,也就是我们常说的质数,官方解释为在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数.

β. 如何判断其是否为素数?
β1. 初始版本

由定义知,对于一个自然数n, 如果从 2 – n -1之间的任意数 i,n均不能被 i 整除,则 n 为素数. 于是通过一个很简单的for循环,我们便很容易的写出来最简单的素数判断函数!

bool isPrime(int num){
for(int i = 2;i < num;i++){
if(num % i == 0)
return false;
}
return true;
}

β2. 加强版

我们来接着想一下,如果我们对一个数进行判断,最好情况下是被 2 整除后直接被判断为非素数,最坏情况下为遍历一遍判断为素数,所以在不考虑素数与非素数的个数占比的差异的情况下,我们可以大致认为平均下来时间复杂度为O(n/2).
对于一个自然数 n, 如果存在 a * b == n (a <= b),那么必定
存在以下结论:


a <= sqrt(n)
b >= sqrt(n)



同时, 对于一个合数,例如 :


2 * 6 == 12


6 * 2 == 12

在利用 for 循环进行遍历的时候,如果 3 可以将 12 整除 .那么,就可以认定 12 为 合数. 换一种思想,对于一个素数来讲,如果在(int)sqrt(n)+1 之前都没有 i 将其整除,那么之后的 i 也就不会有数据会将其整除,因为 如果 6 可以 将 12 整除, 那么 2 肯定也是可以的. 所以,对于 for 循环的迭代次数我们可以有理论依据的将其减少,得到以下的更高效率的代码

bool isPrime(int num){
for(int i = 2;i * i < num;i++){ // i <= (int)sqrt(num) + 1 也可
if(num % i == 0)
return false;
}
return true;
}

γ. 素数筛
γ1. 打表

这个名词对于参加过一些程序设计比赛的同学应该不会陌生,所谓打表就是讲一些数据预先存起来,在程序运行的时候直接访问,得到一个O(1)的可观时间.
就拿我们这个判断素数来说吧,对于一个程序程序设计比赛来说,数据量是比较大的,如果我们在素数问题上一次又一次的判断,那么一般都会TLE的,因此我们引入了这样一个思想——>空间换时间,即使用一个数组来存储每个数的状态(是否为素数),这样就可以实现 O(1) 的时间复杂度了.

int isPrime[10] = {0,1,1,1,0,1,0,1,0,1}; //此处列出了0-9 十个数的素数状态

γ2. 埃氏筛

然而还有一个问题没有解决,对于几十几百的数,我们还是有那么一点点的精力来预先存储每个数的状态的,但对于很大的数据来说,我们还是束手无策的,因此,素数筛就排派上了很大的用场.素数筛有很多种,这里只给大家讲一种最基本的埃氏筛
思路引用了下面这篇博客,以下为核心思想:

想更深层了解 请戳这篇博客

从2开始 2是素数 那么4不是 6不是 8也不是 10、12、14、16、18、20 都不是 这是9次操作
然后 3 开始 6 9 12 15 18 都不是素数 这是5次操作
然后4 跳过 5 跳过 6 跳过
从7开始 14 不是素数 这是1次操作
后边的 8 9 10 11 12 14 15 16 18 20 都会跳过
而11 13 17 19 都不会操作 因为他们的倍数 大于20了

其中核心思想是如果一个数确定为素数,那么其倍数(2,3,4,…)都不会为素数!

废话不多说了,还是上代码吧~

//
// Created by 29273 on 2020-07-26.
//
#include <iostream>
#include <set>
#include <unordered_map>
#include <map>
#include <cctype>
#include <algorithm>m
#include <string.h>
#include <string>
#include <vector>
#include <cstdio>
using namespace std;
#define maxNum 10000
int prime[maxNum]; // 将素数从小到大存储起来
bool isPrime[maxNum]; // 存储每一个数
int countN;
void Prime(int n){ //埃氏筛
countN = 0;
for(int i = 2;i <= n;i++){
if(!isPrime[i]){
prime[countN++] = i;
}
for(int j = 2; j * i <= n;j++){
isPrime[j*i] = true;
}
}
}
int main(){
Prime(1000);
for(int i = 0;i <= countN;i++){
printf("%d ",prime[i]);
}
return 0;
}

相较于我们对每一个数通过函数进行判断然后存储状态的方法,在之前那篇博客中实验证明过,埃氏筛确实节省了很多的时间.
温馨提示:使用素数筛还是需要要看情况的,比如题目数据最大为1e6 ,那么我们的参数 maxNum 肯定是需要调整的,如果为 maxNum == 1e7 会造成不必要的时间浪费.

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

算法竞赛入门 — 素数筛

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 算法竞赛入门 — 素数筛
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏