前言
线性筛是一种用于找出小于等于给定数值的所有质数的高效算法。它是一种改进版的埃拉托斯特尼筛法,可以在更短的时间内计算出大量的质数。其有时间复杂度低,空间复杂度低,可扩展性强的优点。今天我们就来给大家讲解线性筛的实现。话不多说,我们现在开始!

文章目录

  • 原理
  • 实现
  • 尾声

原理

任何除1外的自然数都可以被质数整除,这是因为若它不含有1和本身以外的因子,则它是质数,被自身整除,否则对其1和本身以外的因子进行同样讨论,即可证明它含有素因子。也就是说我们要判定一个数是不是质数就找出它的的最小质因子,如果最小质因子等于它本身,那么它就是质数。反之它就不是质数。
就拿质数2举例,它的倍数除了2以外全都不是质数。

实现

首先我们要先创建一个数组minp用来储存每个数的最小质因子,然后在创建一个数组prime用来储存质数。我们需要从2到n(指定的数)范围内筛选出来质数,同时求出各个数的最小质因子,我们刚才得知2的倍数的最小质因子全都是2,3的倍数的最小质因子也同样是3,也就是说我们可以通过循环把minp[质数的倍数]的值全部变为该质数的值,这时候我们可能会发现有些会问题,比如6是2的倍数也是3的倍数。那么遍历后它的最小质因子不就变成3而不是2了么?没错是这样的,所以我们需要有这样一句判断如果这个数模上现在遍历到质数等于0我们就停止循环,或者当这个数的最小质因子等于目前遍历到的质数时就停止循环,这样就可以解决刚才的问题(这句话最好看着代码读不然不好理解)。那么我们上代码!

#includeint main(){int prime[100] = { 0 };//质数int minp[101] = { 0 };//最小质因子int cnt = 0;for (int i = 2; i <= 100; ++i){if (minp[i] == 0) {minp[i] = i;prime[cnt++] = i; }for (int j = 0; j < cnt; ++j){int p = prime[j];if (i * p > 100)break;minp[i * p] = p;if (minp[i] == p)break;//if(i%p==0) //用这个也可以//break;}}for (int i = 0; i < cnt; i++)printf("%d ", prime[i]);return 0;}

尾声

今天的线性筛算法就介绍到这里,如果觉得博主讲的不错的话请给博主一个关注,点赞,收藏。博主还将持续分享知识,我们下期再见!