[Java] 백준 #1929 (기본 수학2)

📍 출처

출처 : https://www.acmicpc.net/problem/1929

📝 문제

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

⌨️ 입력

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

🖨 출력

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

⌨️ 예제 입력

3 16

🖨 예제 출력

3
5
7
11
13

📚 내가 제출한 코드

import java.util.Scanner;

public class Main{

	public static boolean[] prime;

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);

		int num1 = sc.nextInt();
		int num2 = sc.nextInt();

		prime = new boolean[num2 + 1];
		get_prime();

		for(int i = num1 ; i <= num2 ; i++){
			if(!prime[i]) System.out.println(i);
		}
	}

	public static void get_prime(){
			//false : 소수, true : 소수X
			prime[0] = true;
			prime[1] = true;

			for(int i = 2; i <= Math.sqrt(prime.length) ; i++){
				if(prime[i]) continue;
				for(int j = i * i ; j < prime.length; j += i){
					prime[j] = true;
				}
		}
	}
}

✏️ 내가 제출한 코드에 대한 설명

이 문제는 에라토스테네스의 체를 사용하여 해결하였다.