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

풀이

범위 안의 소수를 구하는 문제로, 에라토스테네스의 체를 이용하여 푼다.

1. 범위가 1~n까지인 배열 생성
2. 1은 소수가 아니므로 0으로 대체
3. 2를 제외한 2의 배수 모두 0으로 대체
4. 지워지지 않은 다음 수가 3이므로, 3을 제외한 3의 배수 모두 0으로 대체
5. 위 과정을 n의 제곱근까지 반복(이 문제에서는 4)
6. 배열에 0이 아닌 값 출력

소스 코드

import java.util.*;

public class 소수구하기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		
		int[] arr = new int[n+1];
		for (int i = 2; i < n+1;i++) {
			arr[i] = i;
		}
		
		for (int i = 2; i <= Math.sqrt(n); i++) {
			if (arr[i] == 0)
				continue;
			for (int j = i+i; j < n+1; j=j+i) {
				arr[j]  = 0;
			}
		}
		
		for (int i = m; i < n+1; i++) {
			if (arr[i] > 0)
				System.out.println(arr[i]);
		}
	}
}

태클 감사합니다.
조언 환영입니다.