该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定正整数n，输出n以内的质数个数。

Format

Input

一个正整数n，其含义见题目描述。

Output

一个整数，表示答案。

Samples

10

4

Limitation

【样例解释】

10以内有2、3、5、7，共计4个质数。

【提示】

如何判断一个数是否为质数？

• 设这个数为$x$，若对于$2$ ~ $x-1$，都不为其因子，则$x$为质数。

【数据范围】

对于60%的数据，$2\leq n\leq 10$

对于另外20%的数据，$2\leq n\leq 10^3$

对于另外10%的数据，$2\leq n\leq 10^5$

对于另外10%的数据，$2\leq n\leq 10^7$