[백준 / JAVA] 2960. 에라토스테네스의 체

https://www.acmicpc.net/problem/2960

2960번: 에라토스테네스의 체

 

---

💻 풀이 결과

 

💯 최종 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();
		boolean[] check = new boolean[N + 1];
		int cnt = 0;

		Loop: for (int i = 2; i <= N; i++) {
			// 넘기는 조건
			if (check[i]) {
				continue;
			}

			// 여기서 찍히는 것들이 소수이다 !!
			// System.out.print(i + " ");

			// i는 소수이므로 i의 배수를 다 찾아서 check배열 true표시하기
			for (int j = i; j <= N; j += i) {
				// 넘기는 조건
				if (check[j]) {
					continue;
				}

				// check배열 true표시
				check[j] = true;
				cnt++;

				// K 번째 지워진 수 출력
				if (cnt == K) {
					System.out.println(j);
					break Loop;
				}
			}
		}
	}
}

💬 풀이 과정

• N까지 전체 범위의 N+1 크기 숫자 체크 배열을 생성한다.
• 소수를 찾기 위해 2부터 N까지의 수 중에서 체크된 숫자는 패스한다.
• 여기서 패스하지 않은 숫자들이 소수이다.
• 소수를 찾으면 소수의 배수들을 끝까지 돌면서 체크해 준다.
• 반복하며 소수를 찾는다.
• 이 문제에서는 체크하는 순서를 살피는 문제였다.

💡 깨달은 점

1. 에라토스테네스의 체 : 소수를 구하는 방법

• 소수를 찾는 유명한 알고리즘이다.
• 소수를 구하는 데 써먹을 중요한 로직이므로 암기할 필요가 있다.
• O(logN)의 시간 복잡도를 가진다.