๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1929
- M์ด์ N์ดํ์ ์์๋ฅผ ๋ชจ๋ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ฒซ์งธ ์ค์ ์์ฐ์ M๊ณผ N์ด ๋น ์นธ์ ์ฌ์ด์ ๋๊ณ ์ฃผ์ด์ง๋ค. (1 ≤ M ≤ N ≤ 1,000,000) M์ด์ N์ดํ์ ์์๊ฐ ํ๋ ์ด์ ์๋ ์ ๋ ฅ๋ง ์ฃผ์ด์ง๋ค.
- ํ ์ค์ ํ๋์ฉ, ์ฆ๊ฐํ๋ ์์๋๋ก ์์๋ฅผ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ฅผ ํ์ฉํ์ฌ ์ ๋ ฅ๋ฐ์ N๊น์ง ์์๋ฅผ boolean ๋ฐฐ์ด์ ํตํด ๊ตฌํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ1929 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
int N = Integer.parseInt(st.nextToken());
// ์์์ธ์ง ์๋์ง boolean ๊ฐ์ผ๋ก ์ ์ฅ
boolean prime[] = new boolean[N + 1];
// true ๊ฐ์ด ์์ ์๋ ๊ฒ
// false ๊ฐ์ด ์์ ์ธ๊ฒ
// 0๊ณผ 1์ ์์๊ฐ ์๋๋ฏ๋ก true๋ก ๋ณํ
prime[0] = true;
prime[1] = true;
for(int i = 2; i <= Math.sqrt(N); i++){
// i๋ฒ์งธ ์๊ฐ ์์๋ผ๋ฉด
if(!prime[i]){
// i์ ๋ฐฐ์๋ ๋ค i๋ฅผ ์ฝ์๋ก ๊ฐ์ง๊ณ ์์ผ๋ฏ๋ก true๋ก ๋ณํ
for(int j = i * i; j <= N; j = j + i){
prime[j] = true;
}
}
}
// M๋ถํฐ N๊น์ง ์์์ธ ๊ฒ(boolean ๊ฐ์ด false์ธ ๊ฒ๋ค)์ ์ถ๋ ฅ
for(int i = M; i <= N; i++){
if(!prime[i]){
sb.append(i + "\n");
}
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 2108 ํต๊ณํ (2) | 2024.07.22 |
---|---|
[Java] BOJ 1966 ํ๋ฆฐํฐ ํ (0) | 2024.07.21 |
[Java] BOJ 18110 solved.ac (2) | 2024.07.21 |
[Java] BOJ 10845 ํ (4) | 2024.07.20 |
[Java] BOJ 10828 ์คํ (0) | 2024.07.20 |