🤖Algorithm
[백준] 에라토스테네스의 체
Jaeyoung Kim
2023. 1. 25. 13:20
728x90
[백준] 2960번 에라토스테네스의 체 자바
들어가며
오늘은 시간 복잡도를 고려하여 소수를 찾는 알고리즘은 에라토스테네스의 체와 관련 문항에 대해서 정리해보려 한다.
에라토스테네스의 체
에라토스테네스의 체는 소수를 찾는 대표적인 알고리즘이다.
위 이미지는 에라토스테네스의 체의 원리를 잘 나타내고 있다.
원리
- 2부터 소수를 구하고자 하는 구간(N, 위 이미지에서는 120)의 모든 수를 나열한다.(주로 N+1까지의 int 배열을 생성한다.)
- 생성한 int 배열을 for문을 활용, i = 2부터 i <= N까지 탐색하며 intArr[i]==0이면 i를 소수로 간주한다.
- 이후 i부터 i의 배수들을 모두 지운다.(i를 배수로 갖으니 소수가 아니므로)
- 이 과정을 i <= N까지 반복해준다.
위 원리를 활용하여 백준 2960번 문제, 에라토스테네스의 체를 풀이해보았다.
에라토스테네스의 체
문제
에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.
- 2부터 N까지 모든 정수를 적는다.
- 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
- P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
- 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)
출력
첫째 줄에 K번째 지워진 수를 출력한다.
예제 입력 1
7 3예제 출력 1
6예제 입력 2
15 12예제 출력 2
7예제 입력 3
10 7예제 출력 3
92, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.
Solution.java
package baekjoon;
import java.io.*;
import java.util.StringTokenizer;
/* 에라토스테네스의 체 */
// https://www.acmicpc.net/problem/2960
public class baekjoon2960 {
public int solution(int N, int K) {
int answer = 0;
int cnt = 0;
int[] intArr = new int[N + 1]; // 소수를 확인할 배열(에라토스테네스의 체)
for (int i = 2; i <= N; i++) { // 0과 1은 소수가 아니니 제외하고 2부터 N까지 탐색
if (intArr[i] == 0) { // 배열의 값이 0이라면 소수
for (int j = i; j <= N; j += i) { // 해당 소수들의 배수를 탐색하며 값으로 1을 할당
if(intArr[j]!=1) {
cnt++;
intArr[j] = 1;
answer = j;
if (cnt == K) return answer;
}
}
}
}
return answer;
}
public static void main(String[] args) throws IOException {
baekjoon2960 T = new baekjoon2960();
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()); // 소수를 구할 범위 (N까지)
int K = Integer.parseInt(st.nextToken()); // K번째
bw.write(T.solution(N, K) + "\n");
bw.flush();
bw.close();
}
}Reference
728x90