[자바] 백준 2960번: 에라토스테네스의 체

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

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

 

문제에서 명시해준 대로 반복문과 조건문을 작성하면 된다.

 

N+1크기의 boolean형 배열을 만들고,

배열을 모두 true로 초기화 한다.

 

이후 i=2부터, i<n+1까지 i++ 반복문을 돌면서 

아직 지우지 않은 숫자(arr[i]==true인 것)를 찾는다.

해당 숫자와 그 배수를 모두 지우고 카운트를 센다.

카운트가 k가 되었다면 해당 수를 출력한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P2960 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		boolean [] arr = new boolean[n+1];
		for(int i=0;i<n+1;i++) {
			arr[i]=true;
		}
		int count=0;
		
		for(int i=2;i<n+1;i++) {
			if(arr[i]==true) {
				for(int j=i;j<n+1;j=j+i) {
					if(arr[j]==true) {
						arr[j]=false;
						count++;
						if(count==k) {
							System.out.println(j);
							return;
						}
					}
				}
			}
		}
		
		
	}

}