[2960] 에라토스테네스의 체

[Silver IV] 에라토스테네스의 체 - 2960

문제 링크

성능 요약

메모리: 14464 KB, 시간: 128 ms

분류

구현(implementation), 수학(math), 정수론(number_theory), 소수 판정(primality_test), 에라토스테네스의 체(sieve)

문제 설명

에라토스테네스의 체는 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번째 지워진 수를 출력한다.

아이디어

알고리즘 설명대로 구현하면 된다.
배열을 생성할 때 인덱스와 숫자가 같도록 초기화하면 편하다.
배수를 세는 것은 그 숫자만큼 더하면서 건너뛰면 된다.
버퍼에 출력할 때는 toString이 없기 때문에 숫자 출력할 시 형변환해주어야한다.

답안코드

import java.io.*;
import java.util.*;
import java.util.stream.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[] nums = IntStream.range(0, n + 1).toArray();   // 인덱스와 숫자가 똑같도록 만들기 위해 0부터 배열 초기화

        int count = 0;
        for (int i = 2; i < nums.length; i++) {
            for (int j = i; j < nums.length; j += i) {  // 배수 세기 == 그 숫자만큼 더하면서 건너뛰기
                if (nums[j] == 0) continue; // 이미 지워진 경우는 pass

                count += 1;
                if (count == k) {
                    bw.write(String.valueOf(nums[j]));
                    bw.flush();
                    bw.close();
                    return;
                }
                nums[j] = 0;
            }
        }
    }
}

BOJ 카테고리 내 다른 글 보러가기