题目描述

程序细节：如何不超时！ 合理使用break； 尽量让循环少运算； 输出 从2 到n 之间 所有的素数。 如果n也是，也输出n。

输入格式

一个整数n n<=1000000

输出格式

多行数据，每行一个素数，从小到大顺序输出。

样例

input

10

output

2
3
5
7

限制与提示

保证$n\leq 10^6$。

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$