背景

程序细节：如何不超时！ 合理使用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}$