일정 범위 안의 소수 구하기 (에라토스테네스의 체)

1. 개념

고대의 그리스 수학자 에라토스테네스에 의하여 개발된 특정 범위 안의 소수를 구하는 알고리즘

2. Process

범위 안의 수를 나열하고 2부터 시작

2를 빼고 다른 2의 배수를 전부 제거

다음 숫자는 3, 3의 배수를 전부 제거

다음 숫자는 5, 5의 배수를 전부 제거

다음 숫자는 7, 7의 배수를 전부 제거

.

.

.

 

위 방식으로 모든 소수를 골라낼 수 있다.

 

배수를 제거하는 작업은 i*i가 범위 안에 있는 i 까지만 하면 된다.

 

아래 그림에서는 11*11 = 121이므로 11이전 까지만 배수제거를 하면 남은 수는 모두 소수이다.

 

3. GIF로 이해하기

위키백과에서 가져옴

4. 시간 복잡도

O(N log log N) 

 

5. 문제

www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

자바 코드

package Silver;

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

public class P1929소수구하기 {
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		boolean eratos[] = new boolean[N + 1];
		StringBuilder sb = new StringBuilder();
		for (int i = 2; i < N + 1; i++) {
			if (eratos[i])
				continue;
			if (M <= i)
				sb.append(i + "\n");
			if (i < 1001) {
				for (int j = i * i; j < N + 1; j += i)
					eratos[j] = true;
			}
		}
		System.out.print(sb);
	}
}