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

---

1. '에라토스테네스의 체'란
2. 장점 
3. 알고리즘 
4. JAVA로 구현 

---

 

 
 

|  '에라토스테네스의 체'란

 
고대 그리스의 수학자인 에라토스테레스가 만들어 낸 소수를 찾는 방법으로,
마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체' 라고 불린다.
 
 
 

|  장점

 
임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는 간단하고 빠른 방법이다.
즉, 특정 범위 내의 소수를 찾을 때는 에라토스테네스의 체가 가장 빠르다.
 
 
 
 

|  알고리즘

 
에라토스테네스의 체의 알고리즘은 다음과 같다.
 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

그림의 경우, 11² > 120 이므로 11보다 작은 수의 배수들만 지워도 충분하다.
즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

   출처 : 위키백과 - 에라토스테네스의 체 - 

 

---

 
예를들어, n =  64이라는 숫자가 주어졌고 1~64까지의 소수를 전부 구해야 한다 치자.
 
for ( int i = 1;  i <= 64; i++ ) 를 하여 하나 하나 소수인지 아닌지를 확인하는 방법은 비효율적이다. 
에라토스테레스의 체를 쓰면 더 적은 범위로 효율적으로 풀 수 있는데, 제곱을 활용하는 것이다.
 
64의 약수을 구하면 아래와 같고 제곱근은 8이다.

8을 기준으로 왼쪽 숫자와 오른쪽 숫자를 곱하면 64가 나오는데,
오른쪽 숫자는 왼쪽 숫자의 배수로 에라토스테네스의 체로 걸러내면 소수가 아닌 숫자들이다.
그렇기 때문에 i를 2² ~ 8² 까지를 범위로 설정하여 ( ※1은 소수가 아니므로 제외)
i의 배수를 모두 제거해주면 결국 소수들만 남는다.
 
for문 식은 아래와 같다.
for ( int i = 2; i * i <= 64; i++ ){
     for ( int j = i+i; j <= 64; j += i ){    //  i 배수를 찾는 for문
      boolean 배열[ j ] 를 false로 만들어주는 식;
      }
}
 

 => i가 8이 되면 i * i = 64가 되고 8까지만 실행이 된다.

두번째 for문의 i 초기값이 i + i 인 이유는 배수의 기준이 되는 숫자는 소수이기 때문에 제외시켜주는 것이다.
예를들어 i는 2인 경우, 2는 소수이기 때문에 i + i 인 4부터 false를 만들어준다.

두번째 for문으로 인해 배열 안의 소수는 true가 되고 소수가 아닌 수는 false가 된다.
      배열 [ i ] = true인 숫자만 출력하면 소수만 출력된다.
 
 
 
 
 

|  JAVA로 구현

 
백준 1929번 소수 구하기 문제를 예시를 JAVA로 구현해보겠다.
자연수 M과 N이 주어지고 M이상 N이하의 소수를 모두 출력하는 문제이다.
 

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int m = scanner.nextInt();
        int n = scanner.nextInt();

        // n 크기의 boolean 배열을 만듦
        boolean[] prime = new boolean[n + 1];

        // 우선 모두 true로 채우기 (1은 소수이므로 false)
        for (int i = 2; i <= n; i++) { 
            prime[i] = true;
        }

        // n보다 같거나 작을 때 까지 for문 돌리기
        for (int i = 2; i * i <= n; i++) {
            // i의 배수인 숫자를 false로 바꾸기
            for (int j = i + i; j <= n; j += i) {
                prime[j] = false;
                // 소수가 아닌 숫자는 전부 false가 됨 
            }
        }

        // true인 숫자들은 전부 소수.
        // m부터 n의 범위까지 true인 숫자만 출력
        for (int i = m; i <= n; i++) {
            if (prime[i] == true) {
                bw.write(String.valueOf(i) + "\n");
            }
        }
        bw.flush();
        bw.close();
    }
}

 

[JAVA] 백준 1929번 소수 구하기

 
 
 
참고 출처 :

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

 
문제 출처 :

1929번: 소수 구하기