백준_2960 에라토스테네스의 체(자바) / 구현

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_2960 {

	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[] visited = new boolean[N + 1];
		boolean flag = false;

		int t = 0;
		for (int i = 2; i <= N; i++) {
			if(flag==true)break;
			for (int j = i; j <= N; j+=i) {
				if(visited[j]==false) {
					t++;
					visited[j]=true;
				}
				
				if(t==K) {
					System.out.println(j);
					flag = true;
					break;
				}
			}
		}
	}
}

- N 보다 작은 소수를 찾는 알고리즘입니다.

- 방문 처리를 이용해서 중복을 방지했습니다.

- 이중 for 문을 이용해서 모든 경우를 탐색 했습니다.

- 진행하다가 원하는 시점이 오면 조건문을 통해서 출력 및 종료를 합니다.