白駿2960/エラトスのふるい

1197 ワード
白駿 少数 テキストリンク

質問する



に答える


説明:


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
TIL 23|envファイル
[Programmers]10週目-頂点に星を作成