-
Notifications
You must be signed in to change notification settings - Fork 6
Expand file tree
/
Copy path_1929.java
More file actions
64 lines (59 loc) ยท 1.39 KB
/
_1929.java
File metadata and controls
64 lines (59 loc) ยท 1.39 KB
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package backjoon;
//https://www.acmicpc.net/problem/1929
// ์์๊ตฌํ๊ธฐ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class _1929 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
// sol1 memory 39996 run 1732
/*
for(int i=M; i<=N; i++){
int j;
for(j=2; j<=i; j++){
// ์์๊ฐ ์๋๋
if(i % j == 0 && i !=2){
break;
}
if(j*j >= i && i != 1){
System.out.println(i);
break;
}
}
}
*/
// sol2 memory 18316 run 184
boolean[] isNotPrime = new boolean[N + 1]; //๊ธฐ๋ณธ๊ฐ์ด false
isNotPrime[0] = isNotPrime[1] = true;
for (int i = 2; i <= Math.sqrt(isNotPrime.length); i++) {
if (isNotPrime[i]) {
continue;
}
for (int j = i * i; j < isNotPrime.length; j += i) {
isNotPrime[j] = true;
}
}
StringBuilder sb = new StringBuilder();
for (int i = M; i <= N; i++) {
if (!isNotPrime[i]) {
sb.append(i).append('\n');
}
}
System.out.println(sb);
}
}
/*
input
3 16
output
3
5
7
11
13
*/