에라토스테네스의 체
title: 2025-08-18 (날짜) author: 강병호(이름) date: 2025-08-18 (날짜) category: TIL/강병호/2025/08 (파일 경로 : TIL/{이름}/{연}/{월}) layout: post (자유) —
에라토스테네스의 체의 논리를 이용해 구현한 다음 코드이다.
2부터 시작하여 안 지워진 수를 기준으로 그 수의 배수를 지우기 시작한다.
- for문을 통한 반복, 해당 과정에서 이미 지워졌으면 스킵
- for문에서 지워지지 않았다면 그 수에 대한 배수를 지운다. (이미 약수로 존재하는 수이기 때문)
해당 과정에서 문제의 요구 사항 중 하나인 지워진 수를 세기 위해 cnt 변수의 수를 증가시켜줘서 이를 기록하도록 하여 문제를 푼다.
근본적인 에라토스테네스 체의 논리에서 문제의 요구사항을 추가하는 방향으로 이어진다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* @author KBBaeng
* @since
* @see
* @performance
* @category #
* @note
*/
/*
*/
class Main {
static int N;
static int result = 0;
static boolean[] arr = new boolean[1001];
static int cnt = 0;
// static List arr = new ArrayList<>(); // 이미 배수처리 되었는지 확인용
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int primeNum = 2;
for (int i = 2; i <= N; i++) {
// 1. 지우기 처리
if (arr[i]) { // 소수 아님.
continue;
}
// i * j : 배수
int j = 1;
int num = i * j;
do {
num = i * j;
if (arr[num]) {
j++;
} else {
arr[num] = true;
cnt += 1;
if (cnt == K) {
result = num;
break;
}
}
} while (i * j <= N);
if (result != 0) {
break;
}
}
System.out.println(result);
}
}