[알고리즘/자바] 백준 2960번 - 에라토스테네스의 체

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

주어진 N이 소수라면 2보다 크거나 같고 N보다 작은 수로 나눠 떨어지면 안된다. ( 주어진 N이 N>2를 만족하는 자연수 )

 

예를들어 10을 소수인지 판단 하려면 2보다 크거나 같고 9보다 작은 수로 나눠보면된다 ( 10은 소수가 아니기 때문에 2와 5로 나눠떨어진다. )

 

즉 자기보다 작은 수에 의해 나눠떨어지면 소수가 아니다. 이 원리를 이용하면 소수를 빠르게 구할 수 있다. 그 중 대표적인 알고리즘이 에라토스테네스의 체.

 

에라토스테네스의 체는 특정 범위내에 있는 모든 소수를 빠르게 찾기 위한 알고리즘 중 하나이다.

 

 

에라토스테네스의 체를 이용해 2부터 10 사이의 소수를 구하는 방법. 

사라지지 않은 숫자중 가장 작은수인 2의 배수를 모두 제거한다. 

사라지지 않은 숫자중 2다음으로 작은수인 3의 배수를 모두 제거한다.

이런식으로 계속 진행하며 숫자를 지워가다 보면 소수만 남게 된다. 

( 소수가 아닌 수는 자신보다 작은 수에 의해 나눠떨어진다. )

 

 

 

백준 사이트 문제에선 k번째 지워지는 숫자를 찾으라고 한다.

해당 문제의 힌트를 보면 소수인 2와 3도 지우고 있다.  그러니 정확히는 k번째 만나는 수라고 생각하고 풀어야한다.

 

( 문제가 모든 소수를 구하는 것이었다면 P를 만날때 마다 저장하고 지우겠지만 여기선 소수를 구하는것이 목적이 아니기 때문에 지우기만 하고 별도 배열에 저장하진 않는다. )

 

이부분이 조금 헷갈렸는데 이 질문을 보고 이해했다.  글 읽기 - 에라토스테네스의 체와는 관련 없는 문제인가요?? (acmicpc.net)

글 읽기 - 에라토스테네스의 체와는 관련 없는 문제인가요??

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws IOException{
		
		// 입출력
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); 
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		
		String t1 = bf.readLine();
		int n = Integer.valueOf(t1.split(" ")[0]); // n까지 
		int k = Integer.valueOf(t1.split(" ")[1]); // k번째 지워진수
		
		boolean[] remove = new boolean[n+1]; // 지워졌는지 확인하기 위한 boolean 배열
		
		int cnt = 0;
		int ans = 0;
		for(int i=2; i<=n; i++) {
			int by = 1;
			while(i*by <= n) {
				
				if(remove[i*by] == false) {
					remove[i*by] = true;
					cnt +=1;
					if(k == cnt) { // while 종료
						ans = i*by;
						break;
					}
				}
				by +=1;
			}
			if(k == cnt ) break; // for loop 종료
			
		}
		
		bw.write(ans +"\n");
		
	
		bw.flush();
		bw.close();
	}
	
	

		
}