2960번: 에라토스테네스의 체
https://www.acmicpc.net/problem/2960
# 코드
import java.io.*;
import java.util.*;
public class Main {
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());
primeNumber(n,k);
}
// 에라토스테네스의 체 알고리즘
static void primeNumber(int n, int k) {
// n까지 저장할 수 있는 배열 선언
int[] arr = new int[n+1];
// 배열 초기화
for (int i = 2; i <= n; i++) {
arr[i] = i;
}
for (int i = 2; i <= n; i++) {
// 이미 지운 수는 건너뛰기
if (arr[i] == 0) continue;
// 배수들 지우기
for (int j = i; j <= n; j+=i) {
if (arr[j] != 0) {
arr[j] = 0;
k--;
// k번째로 지운 수 출력
if (k == 0) {
System.out.print(j);
return;
}
}
}
}
}
}
- 에라토스테네스의 체 알고리즘 문제이다.
아래 블로그를 참고해 공부했다.
[백준] 2960번 : 에라토스테네스의 체 – JAVA [자바]
https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 문제 문제 풀이 백준 2960번 에라토스테네스의 체는 실버 4
propercoding.tistory.com
'코딩테스트 > 자바 문제풀이' 카테고리의 다른 글
[수학] 백준 21275 폰 호석만 (0) | 2024.08.16 |
---|---|
[수학] 백준 21919 소수 최소 공배수 (0) | 2024.08.15 |
[수학] 9613 GCD 합 (0) | 2024.08.13 |
[수학] 백준 21920 서로소 평균 (0) | 2024.08.12 |
[수학] 백준 4134 다음 소수 (0) | 2024.08.11 |