[백준(baekjoon) 1929] 소수 구하기 / 에라토스테네스의 체

문제

백준 1929

M 이상 N 이하인 소수를 모두 출력하시오. (1≤M≤N≤1,000,000)

해결

알고리즘

두가지 방식으로 풀었다.

1. 소수로 나누기

소수인지 확인하기 위해 자신보다 작은 소수들로 모두 나누어 확인하는 방법

• n개의 수에 자신보다 작은 소수들의 개수k만큼 모두 확인하여야 한다.
• 곱해서 n이 되는 수 중 가장 큰 수인 이하로만 검사하면 된다.

2. 에라토스테네스의 체

소수의 배수들 지워나가는 방법

• O(n log log n) 시간복잡도를 가진다. 자세한 내용
• 방법
  
  1. 소수 여부를 저장해 둘 [N + 1]크기의 배열을 생성한다.
  2. 가장 작은 소수 2부터 시작하여 수들을 차례대로 확인한다.
  3. 지워지지 않은 경우 해당 수는 소수이다. 소수의 배수들을 모두 지운다.
  4. 소수를 i라고 할 때, i * i > N라면 더 이상 수행할 필요가 없으므로 끝낸다.

Q. i * i > N일 경우 왜 더이상 수행할 필요가 없을까?

14까지의 소수를 구한다고 가정하자.

1은 소수가 아니니 건너뛰고, 2부터 확인해보자.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
X

2는 지워지지 않았다. 그러므로 소수이다. 즉, 배수들을 지운다.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
X	O		X		X		X		X		X		X

그다음 3도 지워지지 않았다. 소수이므로 배수들을 지우자.
그런데 굳이 3 * 2 = 6은 확인할 필요가 없다.
6은 이미 나온 소수 2의 배수이기 때문이다.
즉, 3 * 3 = 9부터 확인하면 된다.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
X	O	O	X		X		X	X	X		X		X	X

4는 이미 지워졌으므로 소수가 아니다. 넘어가자.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
X	O	O	X		X		X	X	X		X		X	X

5는 소수이다. 이미 나왔던 소수인 2, 3의 배수는 지워졌다.
즉, 5 * 2 = 10과 5 * 3 = 15는 확인할 이유가 없다.
바로 5 * 5 = 25를 확인하려 했지만, N보다 크다.
그럼 이후에 나오는 소수들의 배수들도 N을 넘길 것이므로 더 이상 수행할 필요가 없다.

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
X	O	O	X		X		X	X	X		X		X	X

구현 java

1) 소수로 나누기

1.import java.util.*;
2.
3.public class Main {
4.    public static void main (String[] args)
5.    {
6.        Scanner stdin = new Scanner(System.in);
7.        int m = stdin.nextInt();
8.        int n = stdin.nextInt();
9.
10.        int[] arr = new int[n+1];
11.        arr[0] = arr[1] = 1;
12.
13.        for(int a:getprime(n)){
14.            for(int i=a+a;i<=n;i+=a){
15.                arr[i] = 1;
16.            }
17.        }
18.        for(int i=m;i<=n;i++){
19.            if(arr[i]==0)
20.                System.out.println(i);
21.        }
22.    }
23.
24.    static ArrayList<Integer> getprime(int n){
25.        int max = (int) Math.sqrt(n);
26.        ArrayList<Integer> prime = new ArrayList<Integer>();
27.        for(int i=2;i<=max;i++){
28.            boolean flag = true;
29.            for(int a=0;a<prime.size();a++){
30.                if(i%prime.get(a)==0){
31.                    flag = false;
32.                    break;
33.                }
34.            }
35.            if(flag == true){
36.                prime.add(i);
37.            }
38.        }
39.        return prime;
40.    }
41.}

2) 에라토스테네스의 체

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int m = sc.nextInt();
7.        int n = sc.nextInt();
8.        int[] check = new int[n + 1];
9.
10.        int i = 1;
11.        while (++i * i <= n) {
12.            if (check[i] == 0) {
13.                if (i >= m)
14.                    System.out.println(i);
15.                for (int j = i * i; j <= n; j += i) {
16.                    check[j] = -1;
17.                }
18.            }
19.        }
20.        while (i <= n) {
21.            if (check[i] == 0 && i >= m)
22.                System.out.println(i);
23.            i++;
24.        }
25.    }
26.}

결과

1. 소수로 나누기
2. 에라토스테네스의 체

1번은 수에 모든 소수들을 나누는 작업을 거쳐 더 느릴줄 알았으나, 2번이 더 느렸다.
2번은 모든 수를 다 확인하는 과정을 거치지만, 1번은 제곱근으로 줄어들고 보유한 소수가 적어서 이렇게 된 것 같다.
수가 더 커지면 다르지 않을까? 하는 생각은 있지만, 1번의 시간 복잡도를 구하지 못해서 잘 모르겠다.