Problem2512--YJY学姐的素数

2512: YJY学姐的素数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 399  Solved: 145
[Submit] [Status] [Web Board] [Creator:]

Description

正常的求素数方式对YJY学姐来说已经low爆了,YJY学姐不喜欢浪费时间,所以她想在最快的时间内求出<=n的素数的个数、

Input

测试数据多组,对于每组测试数据:

输入一个数n(n <= 5000000)

Output

输出从小于等于n的素数的个数sum

Sample Input Copy

5
11

Sample Output Copy

3
5

Source/Category