Problem1189--习题6-1 筛选法求素数

1189: 习题6-1 筛选法求素数

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 12 MB

Submit

Description

从键盘上输入一个正整数N(N<=100),用筛选法求N之内的素数

Input

正整数N

Output

0~N之间的素数,每个素数一行

Sample Input Copy

100

Sample Output Copy

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

筛选法求N以内的素数 

算法: 

(1)挖去1; 

(2)用下一个未被挖去的数P去除P后面各数,把P的倍数挖掉; 

(3)检查P是否小于N的开方的整数部分,如果是,则返回2继续执行,否则就结束。 

(4)剩下的数就是素数。