You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

Input Format

一个整数n n<=1000000

Output Format

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

Sample

input

10

output

2
3
5
7

Hint

保证$n\leq 10^6$。

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

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