[알고리즘] 1929번

오늘 풀어볼 문제는 백준 1929번 문제 "소수 구하기" 이다.

이 문제는 실버3 문제이고 정수론 문제이다.

문제

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

입력

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

출력

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

📌첫 번째 도전📌
소수를 구한다는 건 결국 n이라는 숫자의 배수를 모두 지워주면 된다. 그렇기 때문에 지워주는 과정을 코드로 작성했고, M부터 N까지의 모든 수를 for문으로 확인할 필요까진 없기에 제곱근까지만 수행하게 했다.

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[] A = new int[N+1];

        for(int i=2; i<=N; i++) {
            A[i] = i;
        }
        for(int i=2; i<=Math.sqrt(N); i++) {
            if(A[i] == 0) {
                continue;
            }
            for(int j=i*2; j <= N; j=j+i) {
                A[j] = 0;
            }
        }
        for(int i=M; i<=N; i++) {
            if(A[i] != 0) {
                System.out.println(A[i]);
            }
        }
    }
}

[문제 출처] : https://www.acmicpc.net/problem/1929