백준 2960 / 에라토스테네스의 체

문제

풀이

설명

2부터 N까지의 정수를 에서 입력한 K번째 지워진 수를 구하는 문제이다
에라토스테네스의 체 알고리즘을 알아야 풀 수 있는 문제이며
에라토스테네스의 채 알고리즘에 관한 설명은 다음 링크에서 볼 수 있다.
https://velog.io/@dogit/%EB%B0%B1%EC%A4%80-2581-%EC%86%8C%EC%88%98

코드

import java.io.IOException;
import java.util.Scanner;

public class Num2960 {
	
	public static void main(String[] args) throws IOException {
    	Scanner sc = new Scanner(System.in);
    	int n = sc.nextInt();
    	int k = sc.nextInt();
    	boolean[] check = new boolean[n+1];
    	
    	int cnt = 0;
    	for(int i = 2; i<=n; i++) {
    		for(int j = i; j<=n; j+=i) {
    			if(check[j] == false) {
        			cnt++;
        			check[j] = true;
    			}

    			if(cnt == k) {
    				System.out.println(j);
    				System.exit(0);
    			}
    		}
    	}
    }
}```

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