Home

Jeong-Yoon

26 Dec 2018

Baekjoon1929

소수 구하기

시간제한 메모리제한
2초 256MB

문제

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

출력

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

예제 입력

3 16

예제 출력

3
5
7
11
13

import java.util.ArrayList;
import java.util.Scanner;

public class Problem1929 {
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		int M = scanner.nextInt();
		int N = scanner.nextInt();

		ArrayList<Boolean> primeList = new ArrayList<Boolean>(N + 1);
		primeList.add(false);
		primeList.add(false);
		for (int i = 2; i <= N; i++) {
			primeList.add(i, true);
		}
		for (int i = 2; i * i <= N; i++) {
			if (primeList.get(i)) {
				for (int j = i * i; j <= N; j += i) {
					primeList.set(j, false);
				}
			}
		}
		for (int i = M; i <= N; i++) {
			if (primeList.get(i)) {
				System.out.println(i);
			}
		}
	}
}

다른 사람들이 작성한 코드에서는 Math.sqrt() 함수를 이용해서 제곱근을 사용하였다. 제곱근을 활용하는 방법으로 다시 작성해보자.

Til next time,
Jeong-Yoon at 00:00

scribble