[백준] 2960 - 에라토스테네스의 체 (Java)

문제

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

문제 설명

원래 '에라토스테네스의 체' 알고리즘은 그 숫자의 배수만 지우는데 이 문제에서는 해당 숫자도 지운다. 예를들어 2의 배수를 지울때 원래는 2는 안지우는데 이 문제에서는 2도 같이 지워야 한다.

제출 코드

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

public class Main {
    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer str = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(str.nextToken());
        int K = Integer.parseInt(str.nextToken());

        for(int p=2; p<=N; p++) {
            
            if(q.contains(p) == true) {
                continue;
            }
            else {
                q.add(p);
                for(int i=p*2; i<=N; i+=p) {
                    if(q.contains(i) == true) {
                        continue;
                    }
                    else {
                        q.add(i);
                    }
                }
            }
            
        }

        for(int i=1; i<=N; i++){
            if(i == K) {
                System.out.print(q.poll());  
            }
            else {
                q.poll();
            }
        }
    }
}

결과

---

정리

개념

'에라토스테네스의 채'란?
: 소수가 되는 수의 배수를 지워서 남은 수로 소수를 구하는 방법이다.

<방법>
1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 2를 제외한 2의 배수를 모두 지운다.
3. 남아있는 수 가운데 중에 가장 작은 수인 3을 제외한 3의 배수를 모두 지운다.
4. 남아있는 수 가운데 중에 가장 작은 수인 5를 제외한 5의 배수를 모두 지운다.
5. 이와 같은 방법을 반복하면 구하고자 하는 구간의 소수만 남는다.

주석있는 코드

package BaekJoon_java; 

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

public class boj_2960 {
    static Queue<Integer> q = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer str = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(str.nextToken());
        int K = Integer.parseInt(str.nextToken());


        for(int p=2; p<=N; p++) {

            //이미 지운 숫자인지 확인
            if(q.contains(p) == true) { 
                continue;
            }

            else {
                q.add(p); //숫자 지우기 (큐에 넣기)

                //배수 지우기
                for(int i=p*2; i<=N; i+=p) {

                    //이미 지운 숫자인지 확인
                    if(q.contains(i) == true) { 
                        continue;
                    }

                    else {
                        q.add(i); //숫자 지우기 (큐에 넣기)
                    }
                }
            }
            
        }

        for(int i=1; i<=N; i++) {

            // K번째 지워진 수인지 확인
            if(i == K) { 
                System.out.print(q.poll());  
            }

            else {
                q.poll();
            }
        	
        }
    }

}

느낀점

더 효율적인 방법이 있을 것 같은데 일단 내가 하고 싶은 방법대로 구현해봤다.. 더 연구해보는걸로~