[Algorithm] 에라토스테네스의 체

에라토스테네스의 체
O(Nlog(logN))

[ 소수 규칙 ]

- 1은 소수가 아니다.

- 1과 자기자신으로만 나누어떨어져야한다.

 

[ 에라토스테네스의 체 방법 ]

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성

2. 2부터 시작하며 현재 선택된 숫자의 배수에 해당하는 수를 배열 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다.

3. 배열 끝까지 2를 반복한 후, 배열에 남아있는 수가 모두 소수이다.

 

사진 출처 : https://velog.io/@skdud4659/에라토스테네스의-체소수구하기

 

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

1929번: 소수 구하기

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        try {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int[] input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int M=input[0], N=input[1];

            boolean[] arr = new boolean[N+1];
            arr[0]=true; arr[1]=true; // 소수가 아님
            for(int i=2; i<=Math.sqrt(N); i++){
                if(arr[i]) continue;

                for(int j=i+i; j<=N; j=j+i ){
                    arr[j]=true;
                }
            }

            for(int i=M; i<=N; i++){
                if(!arr[i]) System.out.println(i);
            }
        } catch (Exception e) {
            System.out.println(e);
        }
    }
}