题目描述

筛选法求 1 到 N 之间有多少质数。

输入格式

第一行 1 个正整数：N，范围在[1,1000000]。

输出格式

一个整数。

样例

100

25

1. 复习传统方法找素数

除了 1 和自己，没有其它因数的正整数被称为素数。根据这个定义，判断整数 n 是不是素数，可以可以枚举 2 到 n-1 的所有整数，看当中有没有某个数是 n 的因数，如果有，说明 n 不是素数（是合数），如果没有，那 n 就是素数了。

上面这个方法可以稍稍改良一下，枚举范围缩小到从 2 到 sqrt(n)， 如果没有 n 的因数，那么 n 就是素数。这是因为因数都是成对出现的，如果枚举到 sqrt(n) 都还没找到因数，那就不可能有更大的因数的了，反过来说，如果有一个比 sqrt(n) 大的因数，必然也会有一个比 sqrt(n) 小的因数与之相对应。

#include<bits/stdc++.h>
using namespace std;
bool check(int a)
{
	//我们假定a是大于1的。 
	for(int i=2;i<=sqrt(a);i++)
		if(a%i==0)
			return false;
	
	return true; 
}
int main()
{
	int n;
	cin>>n;
	
	int ans=0;
	for(int i=2;i<=n;i++) //check函数判断1的时候会有问题，这里直接从 2 开始枚举
		if(check(i))
			ans++;
	
	cout<<ans; 

	return 0;
}

2. 筛选法找素数图解

上面的传统方法的主要问题在于效率不够高。要分析从 2 到 n 一批数字，判断每一个数都要从头来，重复计算比较多。另外，有一些题目会反复提问，问题与问题之间有重叠，所以，如果能预先算好了，把中间结果记录下来，回答问题的时候就快很多。为此，我们来学习筛选法求素数。这个方法的本质：就是把整数划分成合数和素数两大类，合数就是若干个质数的乘积（几个质数可以是相同的，例如 4=2*2 ）,比 2 大的整数，要么是合数，要么是质数，我们找到所有的合数，打上标记，那么其余的就是质数了。

下面，我们通过图解来理解整个算法过程。

1. 如果我们要找 2 到 n 的所有质数，那么我们第一步是先画一个表格，将来通过这个表格来标记哪些数是素数，哪些数不是。比方说，n=30，我们要找 30 以内的所有素数，画出来的格子是这样子的：

2. 我们的的操作步骤就是把合数涂上颜色，如果一个格子是比 2 大，而且没有涂颜色，那么它就是质数。因为 1 不是我们关心的数字（我们知道 1 不是合数，也不是素数），直接从 2 开始。 2 没有颜色，所以，我们说 2 就是一个素数。找到了 2 这个素数之后，我们把 2 的所有倍数（不包括 2 本身）都标上颜色，如下图所示

3. 然后我们继续看下一个格子。下一个格子是 3 ，也是没有颜色的，所以，它也是质数。然后，我们又把 3 的所有倍数（不包括 3 本身）涂上颜色，得到下图：

4. 然后我们看下一个格子：4 。 4 已经有颜色了，说明了它是合数（4 是 2 的倍数，我们找到质数 2 的时候，对 4 打了标记）。

5. 然后我们又看下一个格子：5 。 5 没有颜色，说明了它是一个质数。然后，我们把 5 的倍数（不包括 5 自己）都涂上颜色，得到下图：

6. 接着看 6 ，因为有颜色，说明了它是合数（ 6 是 2 的倍数，我们找到质数 2 的时候对 6 打了标记）。

7. 接着看 7 ，它没颜色，说明了它是质数。然后我们又把 7 的所有的倍数都涂上颜色，得到下图：

8. 8 , 9 , 10 都是有颜色的，所以，它们都是合数。

9. 11 没有颜色，说明了它是质数，又把 11 的倍数涂上颜色，得到下图。

10. 我们用同样的方法，一直处理到 30 。在整个过程中，那些没颜色的格子就是质数，我们先后找到了 2,3,5,7,11,13,17,23,29 这些质数。

3. 筛选法找素数的归纳和总结

1. 我们找到一个质数之后，马上给这个质数的倍数（2 倍以上的那些倍数）涂颜色，这个比较好理解，但是为什么找到合数就不需要给这个合数的倍数涂颜色呢？这是因为既然这是一个合数，它就是某个（些）质数的倍数，给它的倍数涂颜色是重复工作。例如 6 是合数，看到它的时候它已经有颜色了，如果你试图给 6 的倍数涂颜色，包括 12,18,24,30，这些格子这个时候都是有颜色的，因为它们是 2 和 3 的倍数，给 2 和 3 的倍数涂颜色的时候已经涂过一遍了。

2. 看格子的时候一定要按顺序，从小到大的看。我们看到 7 的时候，7 的格子没颜色的，是因为从 2 到 6 的质数我们都找到了，对这个质数的倍数标上颜色了。如果我们跳跃着直接去看 77 ，虽然这时候 77 是没有颜色的，但是你不能说 77 就是一个质数。因为 77 的颜色会在找到 7 这个质数的时候才标上，现在才分析完 2~6 的质数，还没那么快能对 77 是否是一个质数下结论。

4. 程序填空

#include<bits/stdc++.h>
using namespace std;
bool f[填空(1) ]; //画好空格子
int main()
{
	int n,i,j;
	cin>>n;
	
	int ans=0;
	for(i=2;i<=n;i++)
	{
		if( 填空(2) ) // 这个格子没有涂颜色，是质数 
		{
			ans++; 
			for(j=填空(3);填空(4)<=n;j++)
				f[填空(5)]=true; //给 i 的倍数涂颜色 
		}
	}
	cout<<ans; 

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}