본문 바로가기
Algorithm/Baekjoon

Baekjoon 2960 에라토스테네스의 체 JAVA

by Hunveloper 2022. 6. 21.
728x90

 

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

2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다.

www.acmicpc.net

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

  1. 2부터 N까지 모든 정수를 적는다.
  2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
  3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
  4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000)

출력

첫째 줄에 K번째 지워진 수를 출력한다.

풀이

에러타소테네스의 체 알고리즘을 따라가면서 값이 지워질 때 마다 cnt를 더해주고,

cnt가 K랑 같은 값이 될때 그 값을 바로 출력해준다.

코드
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt(), k=sc.nextInt(), cnt=0;
		boolean[] chk=new boolean[n+1];
		for(int i=2;i<=n;i++)
			for(int j=1;i*j<=n;j++)
				if(chk[i*j]==false) {
					chk[i*j]=true;
					cnt++;
					if(cnt==k)
						System.out.println(i*j);
				}		
	}
}

 

728x90
728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

Baekjoon 1837 암호제작 JAVA  (0) 2022.06.21
Baekjoon 2061 좋은 암호 JAVA  (0) 2022.06.21
Baekjoon 2581 소수 JAVA  (0) 2022.06.21
Baekjoon 2153 소수 단어 JAVA  (0) 2022.06.21
Baekjoon 11098 첼시를 도와줘! JAVA  (0) 2022.06.21

댓글