[백준] Java - 1929번 : 소수 구하기

- 알고리즘 : 에라토스테네스의 체

- 전체코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        String[] input = br.readLine().split(" ");

        int M = Integer.parseInt(input[0]);
        int N = Integer.parseInt(input[1]);

        List<Integer> list = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            list.add(i);
        }

        for (int j = 2; j < N; j++) {
            for (int k = 2; j * k <= N; k++) {
                list.set(j * k - 1, 0);
            }
        }

        for (Integer n : list) {
            if (n != 0 && n != 1 && n >= M) {
                bw.write(Integer.toString(n));
                bw.newLine();
            }
        }
        bw.flush();
    }
}

- 풀이 과정

1. 1부터 N까지의 List생성(index i의 값은 i + 1)

2. 이중 for문을 사용해서 각 수의 배수들을 제거(set을 통해 0으로 교체), remove사용 시 인덱스가 꼬이게됨

3. 걸러진 list의 요소들을 0과 1이 아니고, M보다 큰 경우 출력