[백준 JAVA] 1929 - 소수 구하기

에라토스 테네스의 체의 알고리즘을 안다면 매우 쉽게 구현이 가능하다!

 

시간복잡도, 메모리 제한은 에라토스 테네스의 체의 시간 복잡도가 O(n*log log n)이기 때문에 충분하다고 판단했다.

내가 생각한 로직은 이렇다

에라토스 테네스의 체 알고리즘 사용
arr[M] ~ arr[N]의 배열에 소수 판별 후 출력

 

[최종코드]

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());

        boolean arr[] = new boolean[1000001];

        for (int i = 0; i < arr.length; i++)
            arr[i] = true;

        arr[0] = arr[1] = false;

        for (int i = 2; i < Math.sqrt(arr.length); i++) {

            if (arr[i]) {

                for (int j = i*i; j < arr.length; j += i)
                    arr[j] = false;
            }
        }

        for (int i = m; i <= n; i++) {

            if (arr[i] == true)
                System.out.println(i);
        }
    }
}

 

배운점

에라토스 테네스의 체 알고리즘을 배워 매우 쉽게 문제를 풀 수 있었다. 이를 통해 알고리즘을 얼마나 알고있음에 따라 문제를 푸는 시간을 얼마나 줄일 수 있는지를 체감하게 되었다!