您的位置: 首页  >  文章  >  素数筛选-埃氏筛法与欧拉筛法

素数筛选-埃氏筛法与欧拉筛法

分类: 文章 • 2024-01-28 20:16:16

1.一般的筛法

根据素数定义，对于一个数n,只要2到sqrt(n）的数无法被n整除即可。相信大家都学过，直接上代码了。

代码：

/*
   简单素数输出：输入一个大于0的整数n，输出1到n之间（不包括该整数）的所有素数，
                 空格隔开（最后一个素数后不输出空格）
Project:prime
Date:    2019/02/28
Author:  Frank Yu
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<stack>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
#define F(i,m,n) for(int i=m;i<n;i++)
//素数判断
bool JudgePrime(int n)
{
	int sqrtn = (int)sqrt(n) + 1;
	F(j, 2, sqrtn)//判断2到sqrtn之间的数能否被n整除 
		if (n%j == 0)
		{
			return false;
		}
	return true;
}
//主函数
int main()
{
	int n,sqrti;
	bool output = false;//控制空格
	scanf("%d",&n);
	F(i, 2, n)
	{
		if (JudgePrime(i))//是素数，则输出
		{
			if (output)
			{
				printf(" %d", i);
			}
			else
			{
				printf("%d", i);
				output = true;
			}
		}
	}
	printf("\n");
	return 0;
}

优化：

看下面部分代码：   

   int sqrtn = (int)sqrt(n) + 1;
    F(j, 2, sqrtn)//判断2到sqrtn之间的数能否被n整除

sqrtn并不是多此一举，sqrt(n)是函数，如果卸载for循环里面,for循环每次都会判断j是否小于sqrt(n),这样的话sqrt函数就会运行多次，但n比较大时，会浪费时间。同样，还有遍历string s时，不要把i<s.length()写在for循环里面。

2.埃氏筛法

时间复杂度：O(n*lglgn)

核心思想：

对于已找到的素数，将它的倍数标记为非素数。

代码：


/*
2013版 王道机试P92 素数筛法
素数输出：输入一个大于0的整数n，输出1到n之间（不包括该整数）的所有素数，
                 空格隔开（最后一个素数后不输出空格）
优化的bug:
n*n不超int即可，否则需要将for (int k = j*j;k < max;k+=j)的j*j改为j*2等，使k的赋值不                   
   超过int，当然,你可以让k是其他类型，不过，数大时，埃氏筛法时间复杂度已经不行了
Project:prime_ai
Date:    2019/02/28
Author:  Frank Yu
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<stack>
#include<iterator>
#include<algorithm>
#include<iostream>
using namespace std;
#define F(i,m,n) for(int i=m;i<n;i++)
#define max 100001
int prime[max];//保存筛得的素数
bool mark[max];//标记该数是否已被标记为非素数 true表示非素数
int primesize;
//素数筛法
void init(int n)
{
	F(i, 0, n)   //初始化
	{
		mark[i] = false;
	}
	memset(prime,0,sizeof(prime));
	primesize = 0;
	F(j,2,n)
	{
		if (mark[j])continue;  //已标记为非素数，跳过
		prime[primesize++] = j;//保存素数
		for (int k = j*j;k < n;k+=j)//标记素数所有倍数为非素数
		{
			mark[k] = true;
		}
	}
}
//主函数
int main()
{
	
	int n;
	bool output = false;
	scanf("%d",&n);
	init(n);
	F(i,0, primesize)
	{
		if (prime[i] < n)
		{
			if(output)
			{
				printf(" %d",prime[i]);//输出空格
			}
			else
			{
				printf("%d",prime[i]);
				output = true;
			}
		}
		else break;
	}
	printf("\n");
	return 0;
}

优化：

标记素数的倍数时,没有从j*2开始，从j*j开始，如果从j*m（m<j）开始，求得m的某个素因子时已经标记过，没必要再标记。

例如,已知素数7,7*4=28在遍历到4的素因子2时已经将2的14倍，即2*14=28标记过了。

优化的bug:

发现这个bug是因为有道题需要40w以内的素数。n*n不超int时即可，否则需要将for (int k = j*j;k < max;k+=j)的j*j改为j*2等（优化失效），使k的赋值不超过int，当然,你可以让k是其他类型，不过，数大时，埃氏筛法时间复杂度已经不行了。                  

3.欧拉筛法  

时间复杂度：O(n)

核心思想：

欧拉筛法是埃氏筛法的优化，非素数仅被最小素因子标记一次。对于一个非素数，它会被它的素因子标记多次，例如,30=2*15=3*10=5*6，在得到素数2,3,5时均被标记一次，数大时更会标记很多次，做了很多无用功。

代码：

/*
素数输出：输入一个大于0的整数n，输出1到n之间（不包括该整数）的所有素数，
空格隔开（最后一个素数后不输出空格）
Project: 欧拉筛法
Date:    2019/02/28
Author:  Frank Yu
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<set>
#include<list>
#include<vector>
#include<map>
#include<stack>
#include<iterator>
#include<algorithm>
#include<iostream>
#define F(i,m,n) for(int i=m;i<n;i++)
using namespace std;
int prime[1000001];//存素数 
bool vis[1000001];//标记非素数，true表示非素数，即合数
int psize = 0;//已知素数个数
void oula(int n)
{
	memset(vis, false, sizeof(vis));//初始化 
	memset(prime, 0, sizeof(prime));
	for (int i = 2; i <= n; i++)
	{
		if (!vis[i])//是素数
			prime[psize++] = i;//保存素数
		for (int j = 0; j<psize && i*prime[j] <= n; j++)
		{
			vis[i*prime[j]] = true;//找到的素数的倍数不访问 
			if (i % prime[j] == 0) break;//相对埃氏筛法的优化，保证合数仅被最小质因子标记一次！ 
		}
	}
}
int main()
{
	int n;
	bool output = false;
	scanf("%d", &n);
	oula(n);
	F(i, 0, psize)
	{
		if (prime[i] < n)
		{
			if (output)
			{
				printf(" %d", prime[i]);//输出空格
			}
			else
			{
				printf("%d", prime[i]);
				output = true;
			}
		}
		else break;
	}
	printf("\n");
	return 0;
}

关键处的解释（重点）：

i%prime[j]==0时，break跳出循环（i是prime[j]的倍数）。这是为什么呢？我们假设继续循环，看看会发生什么。

假设，当i是prime[j]的k倍时，i = k*prime[j]，此时，如果继续for循环，j变j+1，接下来的数就会被prime[j+1]标记，

i*prime[j+1] = k*prime[j]*prime[j+1]，prime里面存的质数，即prime[j]是最小的质因子，prime[j+1]是质因子，某数num=k*prime[j]*prime[j+1]会被prime[j+1]以i倍标记，当i=k*prime[j+1]时，num会再次被prime[j]以k*prime[j+1]倍标记，

违反了欧拉的核心思想，所以才跳出循环。注：num可以分解为多个质因子。
举个例子 ：i = 4 ，j = 1，prime[j] = 2，此时,4*2=8，即8被最小质因子2用4倍标记了。如果不跳出循环，prime[j+1] = 3，4*3 =6*2 =12，也就是说不跳出循环,12会被质因子3（非最小质因子）用4倍标记，当i为6时,会被最小质因子2以6倍再次标记。

加break时的结果：

素数筛选-埃氏筛法与欧拉筛法
加break的结果
素数筛选-埃氏筛法与欧拉筛法
不加break的结果

 我们可以发现，有多个质因子的12=2*6=3*4会被标记两次。没有多个质因子的16=2*8则没有影响，只被标记一次。

更多数据结构与算法实现：数据结构（严蔚敏版）与算法的实现（含全部代码）

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。

相关推荐