白駿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