线性筛（欧拉筛）C语言-Toy模板网

这篇具有很好参考价值的文章主要介绍了线性筛（欧拉筛）C语言。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言
线性筛是一种用于找出小于等于给定数值的所有质数的高效算法。它是一种改进版的埃拉托斯特尼筛法，可以在更短的时间内计算出大量的质数。其有时间复杂度低，空间复杂度低，可扩展性强的优点。今天我们就来给大家讲解线性筛的实现。话不多说，我们现在开始！
线性筛（欧拉筛）C语言,c语言学习,算法专栏,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;
}