[1929] 소수 구하기

[Silver III] 소수 구하기 - 1929

문제 링크

성능 요약

메모리: 24908 KB, 시간: 312 ms

분류

수학, 정수론, 소수 판정, 에라토스테네스의 체

문제 설명

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

입력

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

출력

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

아이디어

많은 수를 탐색해야할 때는 탐색의 횟수를 줄이는 것이 중요하다.
이 문제의 경우

1. 외부 for-loop에서 n의 제곱근까지 탐색하는 것으로 탐색 횟수를 줄일 수 있다.
2. 내부 for-loop에서 i의 제곱부터 탐색을 시작해주면 된다. 그 이하는 이미 이전 loop에서 제거되었을 것이기 때문이다.

또, 소수 문제에서 주의할 점이 하나 더 있다.

1은 소수가 아니다.. 입력 값의 범위를 잘 확인하자

마지막에 출력하는 과정에서 m이 1로 주어지는 상황을 놓쳐서 많은 시간을 삽질했다.
덕분에 시간 초과 문제인가 하고, 최대한 탐색의 수를 줄이는 방향으로 생각해보느라 결과적으로는 좋았지만 실전에서는 주의하도록하자!

답안코드

import java.io.*;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer input = new StringTokenizer(br.readLine());

        int m = Integer.parseInt(input.nextToken());
        int n = Integer.parseInt(input.nextToken());

        int[] nums = IntStream.range(0, n + 1).toArray();
        nums[1] = 0;    // 1은 소수에서 제외!!

        for (int i = 2; i <= (int)Math.sqrt(n); i++) {  // 제곱근까지 loop를 돌리면 전체 횟수를 줄일 수 있음! 2부터 세주어야 함
            if (nums[i] == 0) continue;
            for (int j = i * i; j < nums.length; j += i) {  // 특정 수의 제곱 이상부터 세주면 됨. 그 이하는 이미 이전 loop에서 제거됨
                nums[j] = 0;
            }
        }

        for (int i = m; i <= n; i++) {
            if (nums[i] != 0) bw.write(i + "\n");
        }
        bw.flush();
        bw.close();
    }
}

BOJ 카테고리 내 다른 글 보러가기