#Test1D. 区间素数统计

区间素数统计

区间素数统计

题目描述

给定一个正整数 nn。请编写程序,统计在闭区间 [2,n][2, n] 中共有多少个质数(素数)。

质数是指在大于 11 的自然数中,除了 11 和它本身以外不再有其他因数的自然数。例如 2,3,5,72, 3, 5, 7 都是质数,而 4,6,8,94, 6, 8, 9 是合数。特别地,11 既不是质数也不是合数。

输入格式

输入仅一行,包含一个正整数 nn (2≤n≤10002 \le n \le 1000)。

输出格式

输出仅一行,包含一个整数,表示 [2,n][2, n] 中质数的总个数。

样例

10
4
2
1
20
8

说明/提示

  • 在样例 1 中,[2,10][2, 10] 范围内的质数有 2,3,5,72, 3, 5, 7,共有 44 个。
  • 在样例 2 中,[2,2][2, 2] 范围内只有 22 这一个质数,共有 11 个。
  • 在样例 3 中,[2,20][2, 20] 范围内的质数有 2,3,5,7,11,13,17,192, 3, 5, 7, 11, 13, 17, 19,共有 88 个。