Problem B: 质数的个数

Problem B: 质数的个数

[Creator : ]
Time Limit : 3.000 sec  Memory Limit : 128 MB

Solved: 31Submit: 226Statistics

Description

题目描述

求 1,2,\cdots,N1,2,⋯,N 中素数的个数。

输入格式

一行一个整数 NN。

输出格式

一行一个整数，表示素数的个数。

输入输出样例

输入 #1复制 
10
输出 #1复制 
4

说明/提示

对于 40\%40% 的数据，1 \le N \le 10^61≤N≤106。
对于 80\%80% 的数据，1 \le N \le 10^71≤N≤107。
对于 100\%100% 的数据，1 \le N \le 10^81≤N≤108。

Input

100

Output

25

Sample Input Copy 

1000

Sample Output Copy 

168
Submit