[백준] 1929번. 소수 구하기 (JAVA)

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

---

문제

 

---

풀이

 

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner kb = new Scanner(System.in);
		
		int x = kb.nextInt();
		int y = kb.nextInt();
		
		boolean arr[] = new boolean[y+1];
		
		arr[0] = true;
		arr[1] = true;
		
		for(int i = 2; i < Math.sqrt(y+1); i++) {
			for(int j = i*i; j < y+1; j += i) {
				arr[j] = true;
			}
		}
		
		for(int k = x; k < y+1; k++) {
			if(!arr[k]) {
				System.out.println(k);
			}
		}
		
	}
}

 

소수를 구하는 문제로 에라토스테네스의 체를 이용한 풀이를 진행한다. 

주어진 두 수 사이의 소수를 구하는 문제이지만 별도의 구간에 대한 소수를 찾는 것보단 최종 값까지의 소수를 모두 구한 뒤 다시 구간에 맞는 소수를 출력 하는 것이 더욱 효율적이다.