Problem1045--【筛法】素数统计

1045: 【筛法】素数统计

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 271  Solved: 76
[Submit] [Status] [Web Board] [Creator:]

Description

    输入正整数n(n≤10000000),求小于等于n的素数个数。

      筛法是一种简单检定素数的算法。据说是古希腊的埃拉托斯特尼(Eratosthenes,约公元前274~194年)发明的,又称埃拉托斯特尼筛法(sieve of Eratosthenes)。

Sample Input Copy

6

Sample Output Copy

3

HINT

小于等于6的素数有3个,分别是2,3,5

用筛法统计,效率较高。

Source/Category

数组