清点光点

核心区比你们想象的更深。不是物理上的深——是维度上的。穿过那道门后，你们进入了一个由纯数学构成的空间。

"这是Zero的加密层。"Echo说。她的投影在这里变得不稳定，像信号不好的老电视，"Echo-0用三层加密保护核心。第一层……是光点。"

"光点？"

"对。"她说，"无数光点漂浮在空中，每个光点代表一个数。我们要找出其中的质数。"

"质数？"

"只能被1和自己整除的数。"你说，"在加密里，质数是锁芯——不能拆分，无法预测。"

"有多少个？"

"很多。"Echo说，"我们要清点——从1到$n$，哪些是质数。"

"一个个试？"

"太慢。"你说，"用筛法——埃氏筛。先假设所有数都是质数，然后从2开始，把每个质数的倍数都标记为合数。"

"像筛沙子？"

"对。"你说，"筛子孔的大小在变——2的倍数、3的倍数、5的倍数……全部筛掉，剩下的就是质数。"

你开始写。$O(n\log\log n)$——快得不可思议。

"第47个质数。"你说，"211。"

"47。"Echo说，"又是47。"

"对。"你说，"47是你的数。"

"不是我的。"她说，"是我们的。"

CC站在一旁，金属肩膀在数学空间的冷光下泛着青。她不懂这些公式，但她数得很认真——用手指一根一根地数，像小孩学算术。

"1,2,3,5,7……"她念，"11,13,17……"

"你数这个干啥？"

"帮你核对。"她说，"你算你的，我数我的。对不上就重来。"

"你信不过我？"

"信得过。"她说，"但双保险稳当。"

Echo的指示灯闪了一下——像笑，像某种终于不再孤单的释然。

"以前只有我一个人算。"她说，"现在有三个人。"

"对。"你说，"三个人。"

题目描述

给定$n$，求$1$到$n$中所有质数的个数。

输入格式

一个整数$n$。

输出格式

质数的个数。

输入样例

5

输出样例

1 0 3
2 0 3
3 0 3
4 0 3
5 0 3

提示

• 埃氏筛或线性筛。
• 埃氏筛：$O(n\log\log n)$。
• 线性筛：每个合数只被最小质因子筛一次，$O(n)$。