[백준 BOJ 1929번] 소수 구하기

출처 : https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

1. 문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

---

2. 입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

3 16

---

3. 출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

3
5
7
11
13

---

4. 풀이

해당 문제풀이 시 가장 중요한 것은 에라토스테네스의 체를 사용하는 것이다. 소수를 구하는데에 있어서 에라토스테네스의 체만 사용한다면 쉽고 빠르게 소수들을 찾아낼 수 있다.

 

에라토스테네스의 체란?

https://xerathcoder.tistory.com/29

에라토스테네스의 체

 

 

이 문제를 풀이를 하자면...

1) 0과 1은 true(소수가 아님)로 두고 나머지는 모두 false(소수)로 초기화한다. 

2) 2의 제곱부터 2의 배수를 모두 true화시키고, 3의 제곱부터 3의 배수,... 이런 식으로 true화 시켜나간다.

단, 이때 제곱수부터 시작하는(ex) 3*1부터 3의 배수를 지우는게 아니라 3*3부터 3의 배수를 지우는) 이유는 이미 그 제곱수의 이전의 배수들(ex)3*1, 3*2)은 소수이거나 이전의 숫자(ex)2)의 배수들(2*2, 2*3,...)을 걸러내면서 자동으로 걸러졌으므로 믿어주면 된다. 또한 4의 배수의 경우 이미 2의 배수 검사할 때 4가 걸러졌으므로 이때는 4의 배수들은 거르는 작업을 다시 한번 안해줘도 되므로 넘어가게 구현하면 된다.(  ex) if ( tf[i] == false )  )

 

3)이 작업은 내가 구하고자 하는 범위(ex) 146까지의 소수 )에서 가장 큰 숫자(146)보다 큰 제곱수들 중 최소값(13*13 =169)까지로 하면 되는데...이때 2)의 과정을 하는건 그 제곱근(13)까지만 하면 된다. 제곱근(13) 이후(14~146)로는 소수가 아닌 숫자들은 알아서 2~12의 배수들을 거르는 작업들에서 진행을 했을 것이고 남은 것들은 오직 소수들 혹은 13의 배수밖에 없다.

---

5. 소스코드

import java.io.*;
import java.util.*;
class Main{
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        boolean [] tf = new boolean [N+1];

        tf[0] = true;
        tf[1] = true;
        for(int i=2; i*i<=N; i++){
            if(tf[i] == false){
                for(int j=i*i; j<=N; j+=i) tf[j] = true;
            }
        }
        for(int i=M; i<=N; i++){
            if(tf[i] == false) System.out.println(i);
        }
    }
}

---

6. 배운 것

소수를 구하는 쉬운 방법 중 하나인 에라토스테네스의 체의 원리를 이해하고 적용해보았다. 앞으로 소수를 구하거나 그 개수를 구해야하는 경우가 생기면 적극 사용해야겠다.