소수 구하기(1929)

문제

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

입력

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

출력

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

예제 입력

3 16

예제 출력

3
5
7
11
13

몇 일 전에 풀었던 문제와 똑같은 문제이지만 에라토스테네스의 체라는 알고리즘을 공부해 두어야 할 것 같다.

에라토스테네스의 체 란

소수를 판별하는 알고리즘이고, 소수들을 다량으로 빠르고 정확하게 찾아낼 수 있음

숫자 하나의 소수 확인하는 방법

사실 저번에 문제를 풀때 사용한 방법은, 특정한 숫자의 제곱근까지만 약수가 있는지 확인하게 되면 O(N^1/2)의 시간복잡도를 가진다.

N을 나누게되면 몫이 생기고, 목과 나눈 수 둘 중 하나는 N 제곱근 이하이기 때문

하지만 대량의 소수를 한꺼번에 찾아낼 때는 에라토스테네스의 체를 사용

에라토스테네스의 체 원리

원리는 이러하다. 가장 먼저 소수를 찾아낼 범위만큼 배열을 할당, 해당하는 값을 넣어주고 이후에 하나씩 지워가는 방법을 사용

1. 배열을 생성, 초기화

2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다(자기 자신은 지우지 않고, 이미 지워진 수는 건너뜀)

3. 2부터 시작해서 남아있는 수를 모두 출력

풀이

import java.io.*;
import java.util.*;
public 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());
      //배열을 생성, 초기화
      //여기서 초기화할때는 자기 수로 초기화시켜줌
        int arr[] = new int[N+1];
        for(int i=2; i<=N; i++){
            arr[i] = i;
        }
      //특정수의 배수는 다 지움
      //지운다는 개념을 0으로 잡았음 
        for(int i=2; i*i<=N; i++){
            if(arr[i]==0) continue;
            for(int k=i*i; k<=N; k+=i){
                arr[k]=0;
            }
        }
      //지워진수인 0이 아닌 모든 수를 출력하면 그것이 소수
        for(int i=M; i<=N; i++){
            if(arr[i]!=0){
                System.out.println(arr[i]);
            }
        }
    }
}

백준

에라토스테네스의 체