筛法求素数

Time Limit: 1 Sec Memory Limit: 128 MB
用筛法求之N内的素数。

传送门:SHUOJ1023

Input

N

Output

0~N的素数

Sample Input

1
100

Sample Output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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

题解

复习一下筛法= =

AC code:(不包含输入类)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
boolean[]prime=new boolean [n+1];
Arrays.fill(prime, true);
prime[0]=false;
prime[1]=false;
for(long i=2;i<=n;i++){
if(prime[(int)i]){
System.out.println(i);
for(long j=i*i;j<=n;j=j+i){
prime[(int)j]=false;
}
}
}
}

}

}