자바 - 구현 - 백준 2960 에라토스테네스의 체

문제

---

 

 

 

 

문제해결

---

import java.util.Scanner;

public class B2960 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		boolean[] numbers = new boolean[n+1];
		int idx = 0;
		for(int i=2;i<=n;i++)
			for(int j=i;j<=n;j+=i) {
				if(numbers[j]==false) {
					idx++;
					numbers[j] = true;
				}
				if(idx==k) {
					System.out.println(j);
					return;
				}
			}
	}
}

- n+1 크기의 boolean 배열을 생성해 인덱스가 n에 매칭되게 한다

- 반복문을 돌려 가장 작은수의 배수를 하나씩 지운다(boolean 배열의 값을 true로 바꿈)

- 지울때마다 idx가 하나씩 증가하며, idx가 k와 같을 경우 방금 지워진 값을 출력하고 실행 종료시키면 끝