筛选法的应用—求素数

题目描述
用筛选法求n以内的素数。筛选法求解过程为：将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。数组中不为0 的数即为素数。
输入描述:
多组输入，每行输入一个正整数（不大于100）。
输出描述:
针对每行输入的整数n，输出两行，第一行，输出n之内（包括n）的素数，用空格分隔，

第二行，输出数组中2之后0 的个数。每行输出后换行。
示例1
输入

20

输出

2 3 5 7 11 13 17 19
11

解：

#include<iostream>

using namespace std;

int main ()
{
    int n,result=0;
    int num[100];
    while(cin>>n)
    {
         for(int i=2;i<=n;i++)  //将2~n之间的正整数放入数组
         {
             num[i]=i;    //给数组赋值 
         }
         
        for(int i=2;i<=n;i++)  //遍历数组
        {
            for(int j=i+1;j<=n;j++)   //将数组中2之后的所有能被2整除的数清0，
									//再将3之后的所有能被3整除的数清0
									//以此类推，直到n为止。数组中不为0 的数即为素数
            
			if(num[j]%i==0)   //被n整除即%n==0！！！！！
            {
                num[j]=0;
            }
        }
        for(int i=2;i<=n;i++)
        {
            if(num[i]!=0)
                cout<<num[i]<<" ";
            else
            {
			result++;      //输出2之后的零的数
			}
        }
        cout<<endl;
        cout<<result<<endl;
    }
}

假定题目为输出n以内的所有素数

一般方法 

最容易理解的一个方法，从0遍历到根号n判断n是否能被整除。使用时只需要记住判断到根号n就可以了。

但是时间复杂度是o（n*sqrt（n）），效率略低。

代码如下：

#include<iostream>
#include<cmath>			//用sqrt()这个函数需要加的头文件 
using namespace std;
int prime(int n)
{
	for(int i=2;i<sqrt(n);i++)		//不需要到n，到根号n就已经足够 
	{
		if(n%i==0)	return 0;		//不是素数返回0，是素数返回1 
	}
	return 1;
}
int main()
{
	int n;
	cin>>n;
	
	for(int i=1;i<=n;i++)
	if(prime(i))	cout<<i<<" ";	//如果是素数就打印在屏幕上 
	
	return 0;
} 

普通筛——埃拉托斯特尼(Eratosthenes)筛法

基本思路：

定义一个长度为maxn的布尔变量数组prime[maxn]，数组元素为0则代表所对应的下标为素数，数组元素为1则代表所对应的下标为合数。（下文中2代表prime[2]，2的值为prime[2]的值）

我们先把数组里所有元素的值设为1，代表着目前所有小于n的数都被认为是素数。

假设有一个指针，当他指向2时，2的值为1，表示2为素数，程序把2的倍数4，6，8等的值全部设置成0，这代表他们不被认为是素数。

然后那个指针指向3，3的值为1，表示3为素数，程序把3的倍数6，9，12等的值全部设置成0，这代表他们也不被认为是素数。

指针指向了4，4的值已经被指针指向2时设置成了0。它不是素数，没有必要把它的倍数的值也设置成0，因为4能筛掉的合数，2也都能筛掉。

然后就是指针不断的向后移动，找到素数的值，把它们的倍数的值全部设置成0，直到筛到根号n

因为这种算法是层层筛选素数，所以叫筛法求素数。

函数体代码如下：

const int maxn=10000;						//具体的maxn看题目要求 
bool prime[maxn];
void judge_prime(int n)
{
	memset(prime,1,sizeof(prime));			//把prime数组全部初始化为1 
	for(int i=2;i<n;i++)					//for循环可以实现上面所说的指针的功能 
	{
		if(prime[i]==1)						//找到素数 
		for(int j=i*2;j<=n;j+=i)			//把n以及n以内i的倍数的值全部设为0 
		{
			prime[j]=0;
		}
	}	
}

memset（a,b,c）将a这个地址之后c个字节的值全部替换为b

sizeof（a），返回a总共所占的字节数

第一个循环来找素数，第二个循环来枚举那个素数的倍数

上面讲到的这种方法其实有优化的空间，j刚开始不需要设为2i，可以优化为i*i，指针也和基础方法一样，不用指到n，只需要指到根号n（我也不知道为什么，问数学家去）

优化前的时间复杂度有o（nloglogn），优化后就大概接近o（n）了

优化后的总体代码如下：

#include<iostream>
#include<cmath>
#include<string.h>							//包含memset的头文件，也可以写成cstring 
using namespace std;
const int maxn=10000;						//具体的maxn看题目要求 
bool prime[maxn];
void judge_prime(int n)
{
	memset(prime,1,sizeof(prime));			//把prime数组全部初始化为1 
	prime[0]=0;prime[1]=0;					//加上这两句显得更严谨（ 
	for(int i=2;i<n;i++)					//for循环可以实现上面所说的指针的功能 
	{
		if(prime[i]==1)						//找到素数 
		for(int j=i*2;j<=n;j+=i)			//把n以及n以内i的倍数的值全部设为0 
		{
			prime[j]=0;
		}
	}	
}
int main()
{
	int n;
	cin>>n;
	judge_prime(n);
	for(int i=0;i<=n;i++)
	{
		if(prime[i])						//如果prime[i]=1,也就是i被认为是素数时，输出i 
		cout<<i<<" ";	
	} 
	return 0;
} 

线性筛——欧拉Euler筛

基本思路：

你有没有注意到，埃氏筛法在指针指向2和3时都把6的值设为了0，重复了，所以会有些浪费，终究不能达到o（n）的时间复杂度。

通过离散数学中的知识，我们可以知道每个合数都能分割成一个素数a和另一个数i（可以是素数）的乘积。

那么欧拉筛要做的，就是要保证每个合数只会被分割后的最小素数a筛掉，避免重复。

先放代码，方便理解：

const int maxn=1e7;
bool prime[maxn+5];
int sto_prime[maxn+5];
void judge_prime(int n)
{
	int cot=0;
	memset(prime,1,sizeof(prime));
	prime[0]=0;prime[1]=0;
	for(int i=2;i<n;i++)							//外层循环指向不同的数i 
	{
		if(prime[i])	sto_prime[cot++]=i;			//保存素数到int数组里 
		for(int j=0;j<cot;j++)						//内层循环指向不同的素数 
		{
			if(i*sto_prime[j]>n)	break;			//如果要筛的那个数超出了最大值，退出内层循环 
			prime[i*sto_prime[j]]=0;				//筛数 
			if(i%sto_prime[j]==0)	break;			//最重要的一句， 保证只每个合数只筛一次 
		}
	}	
}

具体到实现上，我们除了要像上面一样定义一个bool类型的数组，还要定义一个int类型的数组，专门用来存放筛选出来的素数。

还需要两层循环来枚举素数sto_prime和另一个数i。

内层从小到大枚举 sto_prime[j]。i×sto_rime[j] 是尝试筛掉的某个合数，其中，我们期望 sto_rime[j] 是这个合数的最小质因数 (这是线性复杂度的条件，下面叫做“筛条件”)。它是怎么得到保证的？

j 的循环中，有一句就做到了这一点：

if(i%sto_prime[j]==0)	break;

j 循环到 哪里 就恰好需要停止的理由是：

• 下面用 s(smaller)表示小于 j 的数，l(larger)表示大于 j 的数。

• ① i 的最小质因数肯定是 sto_prime[j]。

  （如果 i 的最小质因数是 sto_prime[s] ，那么 sto_prime[s] 更早被枚举到（因为我们从小到大枚举质数），当时就要break）

  既然 i 的最小质因数是 sto_prime[j]，那么 i × sto_prime[j] 的最小质因数也是 sto_prime[j]。所以，j 本身是符合“筛条件”的。

• ② i × sto_prime[s] 的最小质因数确实是 sto_prime[s]。

  （如果是它的最小质因数是更小的质数 sto_prime[s]，那么当然 sto_prime[s] 更早被枚举到，当时就要break）

  这说明到 j 之前（用 i × sto_prime[s] 的方式去筛合数，使用的是最小质因数）都符合“筛条件”。

• ③ i × sto_prime[l] 的最小质因数一定是 sto_prime[l]。

  （因为 i 的最小质因数是 sto_prime[j]，所以 i × sto_prime[l]也含有 sto_prime[j] 这个因数（这是因为①），所以其最小质因数也是 sto_prime[j]（新的质因数 sto_prime[l] 太大了））

  这说明，如果 j 继续递增（将以 i × sto_prime[l] 的方式去筛合数，没有使用最小质因数），是不符合“筛条件”的。

欧拉筛因为每个数都只被筛一次，复杂度只有o（n），是最好的筛选素数的方法。

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

一、质数定义

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

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

N有因数的话，那么至少有一半的因数不会超过$\sqrt{N}$。
举个例子，要判断100是不是质数，100 = 10 X 10，只要有1个因数 > $\sqrt{100}$，必然另1个因数 < $\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. 运算结束后，剩下所有未标记的数都是找到的质数。

可以结合下面这张动图理解：

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

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

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

对于步骤5，当 $p^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;
}