[백준] 1929 소수 구하기 java 쉬운 풀이^^

1. 문제 설명 📌

문제 링크

2. 구현 방법 🗃️

KEY WORD: 에라토스테네스의 체

에라토스테네스의 체를 구현해보라고 준 연습용 문제이다. 자세한 설명은 이론을 정리한 링크를 남기겠다.

 

하나 또는 다수의 소수 판별법, 그림으로 쉽게 이해하기

 

(1) 시간복잡도 분석 🕓

범위의 끝을 N이라고 할 때,

$O(N \log(\log N))$

3. 코드 소개 🔎

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


public class Main {
    static int N, M;
    static boolean [] nums;
    static StringBuilder ans = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        nums = new boolean [M + 1];
        prime_shifter();
        for (int i = N; i <= M; i++) {
            if(nums[i]) ans.append(i).append("\n");
        }
        System.out.println(ans);
    }

    public static void prime_shifter(){
        Arrays.fill(nums, true);
        nums[1] = false;
        nums[0] = false;
        for (int i = 2; i <= Math.sqrt(M); i++) {
            if(nums[i]){
                for (int j = i*i; j <= M; j+=i) {
                    nums[j] = false;
                }
            }
        }
    }
}

4. 배운 것들 🎯

에라토스테네스의 체에서 i를 Math.sqrt(M)전까지만 봐도 되는 이유를 잊고 있어서 처음에 OutOfArrayIndex Error를 받았다. 다시 그 이유를 알게 되어서 다행이다. 이유는 이론 링크에 적혀있다.

 

하나 또는 다수의 소수 판별법, 그림으로 쉽게 이해하기