[백준] 1929. 소수 구하기 - JAVA

문제

 

 

---

풀이

 

에라토스테네스의 체를 이용한 문제이다.

 

에라토스테네스의 체 란?

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법이다.

이 방법은 마치 체로 치듯 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 불린다.

 

방법은 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고, 빠른 방법이다.

예를들면 1~100 까지 숫자 중 소수를 찾는다 할 때, 

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

 

100의 제곱근은 10 이다.

그렇다면, 2~10까지 배수를 제거시켜준다.

1. 2를 제외한 2의 배수 제거

2. 3을 제외한 3의 배수 제거

3. 4를 제외한 4의 배수 제거

.

.

.

10. 10을 제외한 10의 배수 제거

이처럼 2부터 100의 대한 제곱근 까지 제거를 해준다면,

소수의 첫 시작점인 2부터 100까지의 소수를 확인 할 수 있다. 

 

이 방법이 '에라토스테네스의 체' 를 이용한 알고리즘이다. 

이 알고리즘은 장점은 시간복잡도가 O(nlogn) 라는 점이다.

 

 

---

코드

 

import java.io.*;

 

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(

            new InputStreamReader(System.in));

        PrintWriter pw = new PrintWriter(System.out);

       

        String[] parts = (br.readLine()).split(" ");

        int M = Integer.parseInt(parts[0]);

        int N = Integer.parseInt(parts[1]);

        int[] arr = new int[1000001];

       

        //배열초기화

        for(int i=0; i<arr.length; i++){

            arr[i] = 1;

        }

       

        //배열에서 소수만 남기기

        for(int i=1; i<Math.sqrt(arr.length); i++){

            if(i==1){

                arr[i]=0;

            }

            if(i>=2){

                for(int j=i*i; j<arr.length; j+=i){

                arr[j]=0;

                }    

            }

        }

       

        //M~N까지 소수만 출력

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

            if(arr[i]==1){

                pw.println(i);

            }

        }

        pw.flush();

        pw.close();

        br.close();

    }

}

 

핵심 코드

 

제곱근을 구하는 Math.sqrt();

그리고 for문을 통해서 배열을 초기화 후

2~Math.sqrt(N) 까지 제곱근을 제외한 제곱근의 배수를 지우는 for문이다.