[BAEKJOON] 1929번 : 소수구하기 (JAVA)

- 알고리즘 분류 : 에라토스테네스의 체

- 사용 언어 : JAVA

- 문제 요점

1. 두 수 사이의 소수를 모두 구하는 문제
2. 에라토스테네스의 체를 이용하여 풀이하면 비교적 간단하게 풀이 가능 

 

소스 설명은 주석을 참고해주세요.

 

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

public class Main {

	//각 수가 소수인지 아닌지 (true : 소수, false:소수X)
	public static boolean[] arr;
	
	// 에라토스테네스의 체 이
	public static void checkPrimeNumber(int start, int end) {
		
		// 2부터 제곱근까지만 확인 
		for(int i=2; i<=Math.sqrt(end); i++) {
			// 소수일 경우 
			if(arr[i] == true) {
				// 그 수의 곱들은 소수가 아님 
				for(int j=2; i*j<=end; j++) {
					arr[i*j] = false;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		arr = new boolean[end+1];
		
		// 모두가 소수라고 초기화 
		Arrays.fill(arr, true);
		
		// 0과 1은 소수가 아님 
		arr[0] = false;
		arr[1] = false;
		
		// 소수 확인 
		checkPrimeNumber(start, end);
		
		// 배열을 확인하며  소수만 출력 
		for(int i=start; i<=end; i++) {
			if(arr[i] == true) {
				System.out.println(i);
			}
			
		}
	}

}