Problem Solving/Java
백준 1929번 소수 구하기 에라토스 테네스의 체 활용 문제풀이 ( Java )
TakeKnowledge
2019. 10. 22. 14:47
반응형
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)
www.acmicpc.net
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
|
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] temp = br.readLine().split(" ");
// split
int m = Integer.parseInt(temp[0]);
int n = Integer.parseInt(temp[1]);
// m부터 n까지의 소수를 찾아 출력하라
// n까지 크기의 판별 배열 생성
boolean[] isNotPrime = new boolean[n + 1];
isNotPrime[0] = true;
isNotPrime[1] = true;
for (int i = 2; i <= n; i++) {
// 2부터 n보다 작거나 같은 동안 반복
if (isNotPrime[i] == false) {
// 숫자 i가 소수로 체크되어 있지 않다면
for (int j = i + i; j <= n; j += i) {
// 그 배수를 시작으로 j가 n 보다 커지기 전까지 i만큼 더해가며
isNotPrime[j] = true;
// 그 배수들은 소수가 아니라고 체크한다
}
}
}
for(int i=m; i<isNotPrime.length; i++) {
// m부터 isNotPirme 배열 길이만큼 돌면서
if(isNotPrime[i] == false) {
// isNotPrime이 false면
bw.write('\n');
// 출력
}
}
}
}
|
에라토스테네스의 체를 활용해야 겠다고 생각해놓고
m 이하는 수는 애초에 소수가 아니라고 판별해버리고 시작했던 내가 나빠..
예시로 주어진 테스트 케이스 넣고 돌리자마자
소수 목록에서 4를 보고 빡대가리임을 다시 한번 한탄했다..
반응형