2주차. 소수구하기

1929. 소수구하기
https://www.acmicpc.net/problem/1929

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

  
- 예제1

  📝입력
  3 16

  💻출력
3
5
7
11
13
  

    
📌풀이
1. 에라토스테네스의 체 (37296 KB,1008 ms)
   

package week2;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 소수구하기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        solution(start, end);
    }

    public static void solution(int start, int end){
        boolean[] check = new boolean[end+1];
        // 2미만은 소수가 아님
        if(end < 2) return;

        // end = Math.sqrt(end) * Math.sqrt(end)
        // a * b = end = √end * √end 이므로, i<=√end
        for(int i = 2; i <= Math.sqrt(end); i++){
            if(check[i] == false){
                for(int j = i*i; j <= end; j= j+i){
                    check[j] = true;
                }
            }
        }

        if(start < 2) start = 2;

        StringBuilder sb = new StringBuilder();
        for(int k = start; k <= end; k++){
            if(check[k] == false) sb.append(k).append("\n");
        }
        System.out.print(sb);
    }
}

   - 에라토스테네스의 체 란?
    - 체크하지 않은 작은 수를 찾아 그 배수들을 체크해준다.
    ex) 2의 배수 4,6,8... 소수가 아니므로 체크배열에서 true처리. 차례대로 3의 배수, 4의 배수를 체크한다.
    - 체크할 숫자의 제곱근 만큼 수행한다. 굳이 그 이상을 체크할 필요가 없기때문이다.
    - a \* b = end = √end * √end 이므로, i<=√end
   - 시작 점부터 끝까지의 소수들을 체크한 후 체크배열을 토대로 소수를 출력함
   - 에라토스테네스의 체를 활용한다면 시간복잡도를 줄일 수 있다.(O(NloglogN))