线性筛（欧拉筛）C语言

阅读本书更多章节>>>>

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

文章目录

原理实现尾声

原理

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

实现

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

#include<stdio.h>int 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;}

尾声

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

阅读本书更多章节>>>>

本文链接：https://www.kjpai.cn/xuetang/2024-03-24/147719.html，文章来源：网络cs，作者：淼淼，版权归作者所有，如需转载请注明来源和作者，否则将追究法律责任！