欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

详解埃氏筛选法筛选质数(C++实现)

程序员文章站 2024-03-21 15:28:10
...

说明:篇中的nN都是同一个意义,大小写不过是为了表现具体和一般形式而已,穿插着用可能让读者容易混淆,请多体谅。

一、质数定义

指在大于1的整数中,只能被1和它本身整除的数。

二、埃氏筛选法最重要的结论:

N有因数的话,那么至少有一半的因数不会超过N\sqrt{N}
举个例子,要判断100是不是质数,100 = 10 X 10,只要有1个因数 > 100\sqrt{100},必然另1个因数 < 100\sqrt{100},这样只要判断10以内有无100的因数即可,使用这种方法的时间复杂度为O(n*√n)。
可能这样你还不是很懂,继续往下看。

三、找到[0,n]范围内所有素数 的算法基本思路

  1. 首先将0、1排除:

  2. 创建从2到n的连续整数列表,[2,3,4,…,n];

  3. 初始化 p = 2,因为2是最小的质数;

  4. 枚举所有p的倍数(2p,3p,4p,…),标记为非质数(合数);

  5. 找到下一个 没有标记 且 大于p 的数。如果没有,结束运算;如果有,将该值赋予p,重复步骤4;

  6. 运算结束后,剩下所有未标记的数都是找到的质数。

可以结合下面这张动图理解:
详解埃氏筛选法筛选质数(C++实现)

四、应用埃氏筛选法优化后的思路

我们发现 [0, N] 范围内很多 > N\sqrt{N}的数其实是[0, N\sqrt{N}]范围内数的倍数。而 > N\sqrt{N} 且 非[0, N\sqrt{N}]范围内数字的倍数的,都是质数。
举个例子: [0, 100] 范围内很多 > 100\sqrt{100}的数其实是[0, 100\sqrt{100}]范围内数的倍数(12,14,16是2的倍数,12,15,18是3的倍数…)。而 > 100\sqrt{100} 且 非[0, 100\sqrt{100}]范围内数字的倍数的(11,13,17…),都是质数。

所以对 标题三 的基本算法思路做出如下优化:
对于步骤4,可以不用从2p开始排除,而是直接从 p2p^2 开始。理由已经在开始讲过,所有的小于 p2p^2 的合数都有更小的因数而被排除。

对于步骤5,当 p2p^2 > n 的时候停止计算。


参考链接:
《使用埃拉托色尼筛选法在21亿内快速查找质数》
《埃拉托色尼筛选法巧解质数问题》


当范围在int范围内:

#include<iostream>
#include<cstdio>
using namespace std;
    
const int maxn=5000000;
long prime[maxn];    // 存储一个个确定为质数的数
bool is_prime[maxn+1];    // 标记范围内所有数
int p = 0;
int sieve(int n)
{
 	p = 0;
	for(int i=0;i<=n;i++)
		is_prime[i]=true;       // 所有数先标记为true
    is_prime[0] = is_prime[1] = false;   // 把数字0,1标记为质数
    for(int i=2;i<=n;i++)
    {
       	if(is_prime[i])         // 如果这个数没有被标记为false
    	{
             prime[p++]=i;       // 用prime数组存起来这个数,既存起了质数,又用p表示了质数个数
             for(int j=i*i;j<=n;j+=i)   // 这里没有优化时的写法是for(int j=2*i; j<=n; j++)。
	    	//因为小于j(即i^2)内的合数都因为(根号j)(即i)内有更小的j的的因数而被排除
    							// 比如3^2 = 9,为什么不算2*3 = 6呢, 因为6<9,所以6因为3以内有更小的因数而直接被排除
    				is_prime[j]=false;
        }
    }
    return p;          // 返回质数个数
}
int main()
{
	int n;
	while(~scanf("%d",&n))
    {
    	printf("质数个数是: %d\n",sieve(n));
    	printf("质数有:\n");
    	for (int i = 0; i<p; i++)
    	{
    		printf("%d ", prime[i]);
    		printf("\n\n");
        }
   	}
    system("pause");
}	

当范围超过了int

static const int N = 1e7;
bool is_prime[N];   // 判断是否是素数
ll prime[N];       // 存储素数
ll sieve(ll num)
{
	int inx = 0;
	for (int i = 0; i<=N; i++)
		is_prime[i] = true;

	is_prime[0] = is_prime[1] = false;

	int MIN = (num > N) ? N : num;

	for (ll i = 2; i<=MIN; i++)
	{
		if (is_prime[i])
		{
			prime[inx++] = i;

			for (ll j = i*i; j<=num; j+=i)
				is_prime[j] = false;
		}
	}
	return inx;
}

int gcd(int inx)    // 此处由于传进来都是质数,所以直接相乘即为gcd
{
	int res = 1;
	for (int i = 0; i<inx-1; i++)
		res *= prime[i];
	return res;
}

void C3()
{
	ll num;     // 输入数
	int p;       // 最小公约数

	cin >> num;

	int inx = sieve(num);   // 筛选素数

	cout << gcd(inx) << endl;
}
相关标签: C/C++算法及题解