#O1021. 素数个数

素数个数

题目描述

求 1∼n1 \sim n 中素数的个数。

题目类型

筛法、数论

输入格式

一行一个整数 nn。

输出格式

一行一个整数,表示 1∼n1 \sim n 中素数的个数。

样例 #1

样例输入 #1

10

样例输出 #1

4

数据规模与约定

数据范围 说明
1≤n≤1071 \le n \le 10^{7} 上界
  • 请使用欧拉筛或埃氏筛,O(nn)O(n \sqrt{n}) 的做法会超时。