Problem F: 筛法求之n内的素数

Problem F: 筛法求之n内的素数

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 100  Solved: 76
[Submit] [Status] [Web Board] [Creator:]

Description

素数指在大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数(也可定义为只有1和本身两个因数的数)。比1大但不是素数的数称为合数。1和0既非素数也非合数。素数在数论中有着非常重要的地位。

用筛法求之n内的素数。筛法是效率较高的求n以内的经典算法,也可以使用其他方法来解决本问题。

Input

n

Output

0~n的素数

Sample Input

100

Sample Output

2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

HINT

数组大小动态定义?函数?