728x90
문제
에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.
이 알고리즘은 다음과 같다.
- 2부터 N까지 모든 정수를 적는다.
- 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
- P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
- 아직 모든 수를 지우지 않았다면, 다시 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 |
댓글