[99클럽 6기/Java] 백준 1929 - 소수 구하기

문제 - 백준 1929

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

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

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

풀이

• 입력값의 범위가 크기 때문에 에라토스테네스의 체 대신 for문을 사용했다.
• $N$을 2부터 $\sqrt{N}$까지의 수로 나누면서 나머지가 0이면 합성수, 그렇지 않으면 소수로 판정했다.
• 입력값인 $M$ 이상 $N$ 이하의 모든 수에 대하여 위 과정을 반복했다.

핵심 포인트

• 어떤 수 $N$이 합성수이면, $N$의 소인수 중 적어도 하나는 $\sqrt{N}$ 이하에 존재한다.
• 즉, $N$까지 전부 탐색하지 않아도 $N$의 약수를 찾을 수 있다. ($O(\sqrt{n})$)

코드

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

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

		final int M = Integer.parseInt(st.nextToken());
		final int N = Integer.parseInt(st.nextToken());

		for(int i = M; i <= N; i++)
			if(isPrime(i)) System.out.println(i);
	}

	public static boolean isPrime(int n) {
		if(n == 1) return false;
		for(int i = 2; i * i <= n; i++)
			if(n % i == 0) return false;
		return true;
	}
}

채점 결과