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

 문제

www.acmicpc.net/problem/2960

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

2960 에라토스테네스의 체

 

 구현 방법

 에라토스테네스의 체을 배경으로 구현하였고 문제 조건에 맞춰 조금씩 수정하였습니다.

이중포문을 돌려서 i가 2부터 N까지 내부 포문은 j는 i부터 N까지 i를 더해가며(배수) 반복해줬습니다.

해당 값이 이미 true라면 그냥 넘어가고 방문한 적이 없는 값이라면 방문처리를 해주고 카운트를 세주었습니다.

카운트가 K와 같으면 해당 값을 출력해주면 끝!

 

 구현 코드

package BOJ.Silver.구현;

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

public class B2960_에라토스테네스의체 {
	static boolean[] arr;
	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());
		
		arr = new boolean[1005];
		int cnt = 0;
		stop:for (int i=2;i<=N;i++) {
			for (int j=i;j<=N;j+=i) {
				if (!arr[j]) {
					cnt++;
					arr[j] = true;
					if (cnt==K) {
						System.out.println(j);
						break stop;
					}
				}
			}
		}
	}
}

 

정답!