素数筛-试除法 埃氏筛 线性筛

✨✨ 欢迎大家来到小伞的大讲堂✨✨养成好习惯先赞后看哦~所属专栏算法小伞的主页xiaosan_bloggitee:许星让 (xu-xingrang) - Gitee.com制作不易点个赞吧谢谢喵定义质数(素数)是指在大于 1 的**自然数**中除了 1 和它本身以外不再有其他因数的自然数。根据素数这一定义可以提炼出几点内容素数是自然数因此是整数素数是大于1的自然数因此小于等于1的数字都不是素数包括负数0和小数素数只有两个因数1和自身结合1,2,3点可以推断出在自然数范围内最小的素数是21.试除法这应该是最容易想到的我们只需要在[ 2sqrt[n] ]范围内找到一个数逐一枚举数字对每一素数尝试用n去除。如果可以被整除则说明枚举的数字是n的因子。根据素数定义数字n非素数如果不可以被整除则需要继续往后枚举查看其他枚举数字相除之后的结果如果后面有可以被整除的数字则结果和上面第一条一样。如果在[ 2sqrt[n] ]范围内都没有可以被整除的数字则说明数字n在[1n]范围内只有1和n两个因子因此n是素数。#define n 10010 vectorbool isPrime(n 1, true);//标记i位置是否为素数 void init_prime() { for (int i 0; i n; i) { if (i 1) isPrime[i] false; else for (int j 2; j sqrt(i); j) { //小于等于sqrt(i)的位置当sqrt(i)jn时其中i%j只会在(0,1)中所以减去多于的枚举 if (i % j 0) { isPrime[i] false; break; } } } }如果只对于一个数是否为素数其中的On(sqrt(n));1.1 剪枝我们发现素数一定是除了2以外的奇数#define n 10010 vectorbool isPrime(n 1, true);//标记i位置是否为素数 void init_prime() { for (int i 0; i n; i) { if (i 1) isPrime[i] false; else if (i ! 2 i % 2 0) { isPrime[i] false; } else { for (int j 2; j sqrt(i); j) { //小于等于sqrt(i)的位置当sqrt(i)jn时其中i%j只会在(0,1)中所以减去多于的枚举 if (i % j 0) { isPrime[i] false; break; } } } } }2. 素数筛-埃氏筛(埃拉托斯特尼筛法)一般用于对一整块的区间进行标记用于判断多个元素,不如使用试除法剪枝判断单个元素上面的朴素算法以及各种优化方法都是对给定的单一数字进行判断从而得知这个数字是否为素数。但在实际问题中往往需要获取一个区间内所有素数或者在短时间内多次查询判断。应对这样的需求我们会进行预处理对某一区间进行素数挑选把素数挑选出来存储到另外一个地方或者标记起来。接下来介绍的这两种算法正好是把某一区间内的素数都筛选出来且时间复杂度也不高。#define n 10010 vectorbool isPrime(n 1, true);//标记i位置是否为素数 void init_prime() { for (int i 0; i n; i) { if (i 1) isPrime[i] false; else if (isPrime[i]) { for (int j 2; i * j n; j) {//我们标记存在的组合中存在最小的素数 isPrime[i * j] false; } } } }但是这种一会存在一种弊端当我们的值为12时由于122*63*4这样我们标记的时候就会形成重复标记会增加时间复杂度因为我们是素数去乘以自然数可能就会乘到不同素数的倍数导致重复探测3.线性筛我们来分析一下重复标记的原因在上面的埃式筛中当我们遇到素数后将它的倍数全部标记由此可以推断一个数被重复标记的原因是因为它是不同质数的因数。也就是说我们使用了多个质因数去标记了这个合数。例如12被2和3标记过30被2、3、5同时标记过。分析出了原因优化方向就呼之欲出了我们只要使用最小质因数去标记这个数十分重要这是线性筛的核心原理所在就行了具体该怎么做呢具体来说就是维护一个标记数组 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 的遍历。#define n 10010 vectorbool isPrime(n 1, true);//标记是否为素数 vectorint prime;//存储最小素数 void init_prime() { for (int i 0; i n; i) { if (i 1) isPrime[i] false; else { if (isPrime[i]) {//是素数 prime.push_back(i); } for (int j 0; j prime.size() i * prime[j] n; j) { isPrime[i * prime[j]] false; if (i % prime[j] 0) break; } } } }