Problem1645--埃氏筛法统计质数个数

1645: 埃氏筛法统计质数个数

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 437  Solved: 185
[Status] [Submit] [Creator:]

Description

埃拉托斯特尼筛法，简称埃氏筛或爱氏筛，

是一种由埃及数学家埃拉托斯特尼所提出的一种简单检定素数的算法。

最小的素数是2，那么2的整数倍都不是素数，删去4,6,8…
余下的数里，最小的素数是3，删去6,9,12…
最终未被删去的数就是素数

Input

输入一个数n,计算2-n以内有多少个质数? (n<=10000000)
 
 

Output

 

Sample Input Copy 

10000000

Sample Output Copy 

664579

HINT

不使用埃式筛法很可能会超时,只能得70分


做完的同学有兴趣可以去百度比这个方法更快的----欧拉筛法 

Source/Category

 
[Submit] [Status]