题目

用筛选法求n以内的素数。筛选法求解过程为：将2~n之间的正整数放在数组内存储，将数组中2之后的所有能被2整除的数清0，再将3之后的所有能被3整除的数清0 ，以此类推，直到n为止。数组中不为0 的数即为素数

输入描述：

多组输入，每行输入一个正整数（不大于100)

输出描述：

针对每行输入的整数n，输出两行，

第一行：输出n之内（包括n）的素数，用空格分隔，
第二行：输出数组中2之后0 的个数。每行输出后换行

示例：

输入：20
输出：2 3 5 7 11 13 17 19
11

分析过程：

要求n以内的素数，按照题目所给的求解过程的思路，一步一步得出即可

for循环在输出n以内的素数时，用一个变量count对素数进行计数，for循环结束后，输出0的个数，即为n以内非素数的个数，用n-count-1即可，最后要对count进行清0，以便进行下一次运算.

代码实现：

int main() {
	int n = 0;
	int count = 0;
	int num[100] = { 0 };
	//多组输入，每组输入一个正整数(不大于100)
	while (scanf("%d", &n) != EOF) {
		//先将所有数放在数组里
		for (int i = 2; i <= n; i++) {
			num[i] = i;
		}
		//将数组中2之后的所有能被2整除的数清0
		for (int i = 2; i < n; i++) {
			for (int k = 2; k < n; k++) {
				if (num[k] % i == 0 && i != k) {
					num[k] = 0;
				}
			}
		}
		//找出符合要求的数 并打印
		for (int m = 2; m < n; m++) {
			if (num[m] != 0) {
				printf("%d ", num[m]);
				count++;
			}
		}
		//输出2之后0的个数
		printf("\n%d\n", n - count - 1);
		//退出循环前 count归0
		count = 0;
	}
	system("pause");
	return 0;
}

假定题目为输出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），是最好的筛选素数的方法。

题目要求：

用筛选法求100之内的素数。

什么是筛选法？

筛选法指的是“埃拉托色尼筛法”。埃拉托色尼是古希腊的著名数学家，他的方法是：在一张纸上写上1~1000的全部整数，然后逐个判断它们是否是素数，找到一个非素数就将其挖掉，到最后剩下的就是素数。

例如在50个数中找素数：

具体做法为：

（1）先将1挖掉（1不是素数）
（2）用2除其后面的数，将能整除2的数挖掉（2的倍数）。
（3）用3除其后面的数，挖掉3的倍数。
（4）分别用4、5各数作为除数除这些数以后的各数。这个过程一直进行到在除数后面的数已全部被挖掉为止。
事实上，算法可以简化。如果要找1~n范围内的素数表，只须进行到除数为根号n（取整数）即可。

算法步骤：

（1）挖去1
（2）用下一个未被挖去的数p除p后面各数，把p的倍数挖掉。
（3）检查p是否小于根号n的整数部分，如果是则返回（2）继续执行，否则结束。
（4）剩下的数皆为素数。

注意！！！

这里的挖掉并不是说要在数组中删掉这个数，而且如果删掉数组就无法遍历下去了。我当初在做的时候就老想着删掉，但其实把它的值赋为0效果不就是等同了嘛。当遍历数组的时候输出不为0的数就行！！！

C语言代码：求100内的素数：

#include<stdio.h>
#include<math.h>
int main()
{
	int i,j;
	int a[100];
	for(i=1; i<=100; i++)
	{//不用a[0]，只用a[1]-a[100] 
		a[i]=i;
	}
	a[1]=0;// 1不是素数，挖掉1 
	for(i=2; i<sqrt(100); i++)
	{
		for(j=i+1; j<=100; j++)
		{
			if(a[i]!=0&&a[j]!=0)
			{// 不为0就是素数 
				if(a[j]%a[i]==0)
				{//素数的倍数都不是素数 
					a[j]=0;// 不是素数挖掉 
				}
			}
		}
	} 
	for(i=2; i<=100; i++)
	{
		if(a[i]!=0)
		{
			printf("%4d",a[i]);//间隔宽度为4 
		}
	}
}

C++代码，运用vector容器可以实现求1~n的素数：

#include<iostream>
using namespace std;
#include<vector>

int main()
{
	int n=0;
	vector<int>num;
	cin>>n;
	for(int i=2; i<=n; i++)
	{
		num.push_back(i);
	}
	vector<int>::iterator it;
	vector<int>::iterator k;
	for(it=num.begin(); it!=num.end(); it++)
	{
		for(k=it+1; k!=num.end(); k++)
		{
			if(*it!=0&&*k!=0)
			{
				if(*k%*it==0)
				{
					*k=0;
				}
			}
		}
	}
	for(it=num.begin(); it!=num.end(); it++)
	{
		if(*it!=0)
		{
			cout<<*it<<" ";
		}
	}
}