[알고리즘] 에라토스테네스의 체

에라토스테네스의 체

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법.

 

알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 2를 제외한 2의 배수를 모두 지운다.

3. 3을 제외한 3의 배수를 모두 지운다.

4를 제외한 4의 배수를 모두 지운다.  (4는 2^2. 따라서 이미 다 지워져 있을 것)

4. 5를 제외한 5의 배수를 모두 지운다.

5. 위의 과정을 계속 반복하면 구간의 모든 소수만 남아있다.

 

-> 만약 1부터 120까지의 소수를 구한다고 할 때 11보다 작은 수의 배수들만 지워도 된다.

왜냐하면 11^2 = 121로 120보다 크기 때문에. 11^2 > 120

(11*2, 11*3, 11*4, 11*5.....11*10까지는 이미 지워졌기 때문에.)

 

따라서 이 경우에는 2, 3, 5, 7의 배수만 지우면 된다.

(4는 2^2이라 이미 지워졌고, 6의 배수는 2와 3의 공배수이므로 이미 지워졌다.)

 

구현

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 배열에 넣는다.

 

2. for문을 2부터 구하고자 하는 구간의 마지막 수(num)까지 돌린다.

   만약 배열의 값이 0이면 continue로 아무것도 하지 않고 넘어간다.

   이제 i부터 자기자신을 제외한 i의 배수를 모두 지운다.   

    -> "지운다" 라는 의미는 배열의 값을 0으로 바꾼다는 의미

         (0이 아니더라도 지웠다는 의미를 알 수 있는 다른 값도 가능)

여기까지가 소수를 구하는 과정이다.

 

3. 소수를 출력해서 보고싶다면

배열의 index가 2부터 끝까지 for문을 돌리는데 배열의 값이 0이 아니면 출력하면 된다.

 

코드(Java)

package bj1929;

import java.util.Scanner;

public class Main2 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();

		int[] check = new int[num + 1];

		for (int i = 2; i <= num; i++) {
			check[i] = i;
		}

		for (int i = 2; i <= num; i++) {
			if (check[i] == 0) {
				continue;
			}

			for (int j = 2 * i; j <= num; j += i) {
				check[j] = 0;
			}

		}

		for (int i = 2; i <= num; i++) {
			if (check[i] != 0) {
				System.out.println(check[i]);
			}
		}

	}

}

 

 

참고자료

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

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전