[자바] 백준 - 1929번(소수 구하기)

 

문제는 간단합니다. 두개의 자연수 사이에 존재하는 소수를 뽑아내기만 하면됩니다.

이를 어떤 방법으로 꺼낼 것인가가 핵심입니다. 방법은 여러가지가 있습니다. 저는 아래와 같이 해결하였습니다.

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main { 

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		int[] arr = new int[n+1];
		
		for(int i=0; i<arr.length; i++) {     //0부터 n까지 배열에 숫자를 담아줌
			arr[i]=i;
		}
		arr[1]=0;  // 1은 소수가 아님
		
		for(int i=2; i<arr.length; i++) {           //n보다 작은 숫자 중에 소수가 아닌 수를 0으로 바꿈
			  for(int j=2; i*j<arr.length; j++) {
				if(arr[i*j]!=0) {
					arr[i*j]=0;
				}
		   	  }
		}
		
		for(int i=0; i<m; i++) {  //나타내고자 하는 소수의 범위가 m부터 n까지 이므로 m미만의 숫자는 모두 0으로 만들어줌
			arr[i]=0;
		}
		
		for(int i=0; i<arr.length; i++) {  //0이아닌 모든 수를 출력
			if(arr[i]!=0) {
				bw.write(arr[i]+ "\n");
				bw.flush();
			}
		}
	}
}

 

제가 사용한 방법은 m까지의 자연수 중 2부터 시작해서 각 숫자들의 배수를 지워주는 방법입니다.

예를들어 m이하로 존재하는 2의배수인 4, 6, 8, 10, ....를 모두 지워주고 3의 배수인 6, 9, 12....를 지워주고 4의배수, 5의배수....를 지워주며 m이하의 자연수 중 어떤 숫자의 배수가 되는 자연수를 모두 지워주는 것입니다. 그렇게 하면 소수만 남게됩니다.

 

그래서 위와 같이 저는 m이하의 자연수를 모두 배열에 담고 소수가 아닌 숫자의 배열에 0을 담아주어 제거하였습니다. 그리고 n부터 m까지의 소수를 요구했으므로 n미만의 숫자를 모두 0으로 만들어주어 제거하였습니다.

마지막으로 0이 아닌 모든 숫자를 출력하여 소수를 뽑아냈습니다.