题目背景

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。（注意：1不是质数）

题目描述

你需要快速统计出n以内（包括n）的质数个数。

此题60分即可打卡，额外每对一个测试点可多获得一分

输入格式

输入为一个正整数n。

输出格式

输出为一个整数，表示n以内质数的个数。

样例

10

4

1000000

78498

数据范围

对于 $60\%$ 的数据：$1\le n\le 10^4$。

对于 $100\%$ 的数据：$1\le n\le 10^7$。

提示

如果你仔细阅读了下面的提示可以多得一些分数~

叮叮老师想判断一个数x是不是质数，他的思路是这样的：

法一：首先他复习了一下L2-4，使用了最直接也最笨的方法，从2判断到x-1，看一看是否有存在一个因数，结果他只能得60分……

法二：他想到对于一个小于x的正整数num，如果num不能整除x，则num必然不能整除num/x （num = num/x * x）。反之相同。我们又知x=$\sqrt{x}$*$\sqrt{x}$。 如果x除以大于$\sqrt{x}$的数，必得到小于$\sqrt{x}$的商，而小于$\sqrt{x}$的整数已经在2到$\sqrt{x}$的整数试过了，因为就没有必要再试（$\sqrt{x}$, x）范围内的数了。于是他将原来的for循环 for(int i=2;i<x;i++) 改成了 for(int i=2;i*i<=x;i++) 这次他多得了一些分数。

法三：他又想到，除了2以外的偶数一定不是质数，因为都能够整除以2。另外，他知道质数还有一个特点：6x肯定不是质数，因为它能被 6 整除；其次 6x+2 肯定也不是质数，因为它还能被2整除；依次类推，6x+3 肯定能被 3 整除；6x+4肯定能被 2 整除。那么，就只有 6x+1 和 6x+5 (即等同于6x-1) 可能是质数了。所以循环的步长可以设为 6，然后每次只判断6 两侧的数即可。 于是他增加了两个if判断，修改了一下for循环，于是他的代码变成了这样：

bool prime(int x)
{
	if(x==2||x==3) return true;
	if(x%6!=1&&x%6!=5) return false;
	for(int i=5; i*i<=x; i+=6)
		if(x%i==0||x%(i+2)==0) return false;
	return true;
}

这次他终于得了90分~

法四：最后的100分实在想不出来了，于是他百度了一下，发现了一种叫筛法的东西……

先把N个自然数按次序排列起来。1不是质数，也不是合数，要划去。第二个数2是质数留下来，而把2后面所有能被2整除的数都划去。2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去。3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去。这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部质数~