[Java] 백준 풀기 2960 - 에라토스테네스의 체

자바 백준 2960번

실버 4

https://www.acmicpc.net/problem/2960

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

 

 

 

 

 

문제 보기

분류: 수학, 구현, 정수론, 소수 판정, 에라토스테네스의 체

 

 

 

 

 

코드 풀이

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 에라토스테네스 클래스의 인스턴스 생성
        Eratosthenes eratosthenes = new Eratosthenes();
        // K번째 지워진 수를 찾는 메서드 호출
        eratosthenes.findKthRemovedNumber();
    }
}

class Eratosthenes {
    private int N; // 입력으로 받은 수
    private int K; // K번째 지워지는 수
    private boolean[] isPrime; // 소수 판별 배열

    public Eratosthenes() {
        Scanner sc = new Scanner(System.in);
        this.N = sc.nextInt(); // N 입력 받음
        this.K = sc.nextInt(); // K 입력 받음
        this.isPrime = new boolean[N + 1]; // 소수 판별 배열 초기화
        Arrays.fill(isPrime, true); // 모든 수를 소수로 초기화
    }

    public void findKthRemovedNumber() {
        int count = 0; // 지워진 수를 카운트하는 변수
        for (int i = 2; i <= N; i++) {
            if (isPrime[i]) { // 현재 수가 소수인 경우
                for (int j = i; j <= N; j += i) { // 현재 수의 배수를 지움
                    if (!isPrime[j]) continue; // 이미 지워진 수인 경우 건너뜀
                    count++; // 지워진 수 카운트 증가
                    if (count == K) { // K번째 지워진 수인 경우
                        System.out.println(j); // 결과 출력
                        return; // 메서드 종료
                    }
                    isPrime[j] = false; // 지워진 수를 표시
                }
            }
        }
    }
}