728x90
난이도 - 실버 4
문제
에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.
- 2부터 N까지 모든 정수를 적는다.
- 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
- P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
- 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)
출력
첫째 줄에 K번째 지워진 수를 출력한다.
728x90
N+1의 boolean 배열을 만들고 2의 배수부터 해당 인덱스의 배열값이 false면 true로 바꾸고(삭제) count를 1 증가시킨다. count가 K가 될 때까지 반복한다.
import java.io.*;
import java.util.StringTokenizer;
public class Main2960 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
boolean[] isPrime = new boolean[N + 1];
int count = 0;
int result = 0;
for (int i = 2; i <= N; i++) {
for (int j = i; j <= N; j += i) {
if (!isPrime[j]) {
isPrime[j] = true;
count++;
if (count == K) {
result = j;
break;
}
}
}
}
bw.write(String.valueOf(result));
bw.flush();
br.close();
bw.close();
}
}
728x90
'백준 > Java' 카테고리의 다른 글
[백준 자바] 9020번(골드바흐의 추측) (0) | 2024.06.23 |
---|---|
[백준 자바] 17103번(골드바흐 파티션) (0) | 2024.06.23 |
[백준 자바] 4948번(베르트랑 공준) (0) | 2024.06.23 |
[백준 자바] 11653번(소인수분해) (0) | 2024.06.23 |
[백준 자바] 1929번(소수 구하기) - 에라토스테네스의 체 (0) | 2024.06.23 |