[백준 1929] 소수 구하기 - Java (에라토스테네스의 체)

백준의 문제 1929번 소수 구하기를 풀면서 새로 알게 된 내용을 정리해 보았다.

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

 

 

 

 

문제의 요구사항은 M이상 N이하의 자연수 중에서 모든 소수를 출력하는 것이다.

 

처음 시도했던 문제 풀이 방식은 소수의 정의 그대로 1과 자신만을 가지는 자연수를 구하고

이 작업을 반복할때마다 약수가 없다면 그 자연수를 출력했다.

 

 

처음 제출했던 문제 풀이 방식(오답)

import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int m = sc.nextInt();
		int n = sc.nextInt();
		for(int i=m; i<=n; i++) {
			int cnt = 0;
			for(int j=2; j<i; j++) {
				if(i%j==0) {
					cnt++;
				}
			}
			if(cnt==0) {
				System.out.println(i);
			}
		}
	}
}

 

 

m부터 n 사이의 자연수가 1과 자신을 제외한 자연수 중에 한 번이라도 나누어 떨어지는지 확인하여 나누어 떨어지지

않는다면 그 수를 출력했다. 이 방식을 사용하면 모든 자연수마다 1과 자신을 제외한 약수가 존재하는지 확인해야 했기

때문에 많은 반복 작업을 발생시켰고 시간 초과를 초래했기 때문에 더 효율적인 방법이 필요했다.

 

이를 위해 사용한 다음 문제풀이 방식은 에라토스테네스의 체를 활용한 소수 찾기 방법이다.

우선 에라토스테네스의 체에 대해 간략히 설명하겠다.

 

 

에라토스테네스의 체란?

2부터 소수를 구하고자 하는 모든 구간의 수를 나열하고 1씩 증가하는 수마다 자기 자신을 제외한

배수를 모두 소수에서 제외시킨다. 이러한 작업을 반복하고나면 구하고자 하는 소수만 남게 된다.

 

 

이 설명에 따라 코드를 구현해 보면 아래와 같다.

 

import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {
		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; i++) {
			arr[i] = i;
		}

		for (int i = 2; i <= n; i++) {
			if (arr[i] == 0) {
				continue;
			}
			for (int j = 2; i * j <= n; j++) {
				arr[i * j] = 0;
			}
		}

		for (int i = m; i <= n; i++) {
			if (arr[i] != 0) {
				System.out.println(arr[i]);
			}
		}
	}
}

 

 

총 세 가지의 반복 작업을 거치게 되는데 처음 M이상 N이하의 자연수가 담길 배열을 생성하여 수를 넣어준다.

그다음 배열에 담긴 N보다 작은 자연수의 모든 배수를 소수에서 제외시킨다. (소수가 아니면 0으로 치환) 여기서 주의할

점은 모든 4의 배수는 2의 배수에 포함되듯이 이미 제외된 수를 다시 판별하는 똑같은 작업을 거치지 않도록 한다.

위의 모든 작업이 완료되면 남은 수를 출력한다.

 

 

 

 

 

 

 

 

---

Reference

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4