에라토스테네스의 체

소수를 구하는데에 사용되는 효율적인 알고리즘 중에 하나입니다.

소수.. 약수가 자기 자신과 1만 존재하는 숫자를 말합니다.

단순한 반복문으로도 구할 수 있습니다만, 숫자 커질수록 굉장히 비효율 적이기 때문에 이런 경우 사용하면 좋은 알고리즘 입니다.

아래의 이미지는 에라토스테네스의 체를 검색했을 때 흔히 볼 수 있는 이미지 입니다.

 

참고한 블로그

프로그래머스 - 소수찾기 [java]

[Algorithm] 에라토스테네스의 체

 

 

여러 글들을 보았지만, 가장 이해하기 쉽다 싶은 글의 내용을 그대로 가져왔습니다.

소수들을 대량으로 빠르고 정확하게 구하는 방법입니다.

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

 

즉, 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고 이후에 하나씩 지워나가는 방법을 말합니다.

아래의 코드가 이전 문제인 소수찾기 문제에서 다른 분이 작성하신 코드로 에라토스테네스의 체 를 사용한 코드입니다.

https://shsus.tistory.com/139

▲▲ 이전 문제 링크 ▲▲

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        // 받아온 숫자 n의 크기에서 1을 더한 크기의 boolean 빈 배열을 만듭니다.
        // 이후 반복문을 통해 2 ~ n번째 수를 true 로 초기화 합니다.
        boolean[] prime = new boolean[n + 1];
        for (int i = 2; i <= n; i++)
            prime[i] = true;

	// 받아온 n의 제곱근을 구합니다. (반복문의 최대 횟수)
        // 2부터 100까지의 반복문을 돌려서 구합니다.
        // i번째가 소수일 경우 그 배수들을 모두 false로 초기화합니다. (배수는 소수가 아닙니다)
        int root = (int) Math.sqrt(n);
        for (int i = 2; i <= root; i++) {
            if (prime[i] == true) {
                for (int j = i; i * j <= n; j++)
                    prime[i * j] = false;
            }
        }

	// 이후 2부터 n번까지의 숫자들 중 true인 값들의 갯수만큼 answer에 누적시킵니다.
        for (int i = 2; i <= n; i++) {
            if (prime[i] == true)
                answer++;
        }
        return answer;
    }
}

이처럼 에라토스테네스 체를 이용한 방식으로 문제를 풀 수 있습니다.

위는 이전에 풀었던 문제를 토대로 설명한 것이고 아래에는 순수 에라토스테네스 체에 대한 코드만을 적어 놓았습니다.

 

 

public class t {
    public int solution(int n) {
        int answer = 0;
        // 받아온 숫자가 100이락 가정하고 풀이를 시작합니다.
        // 배열의 길이를 받아온 100으로만 하면 99까지의 숫자가 들어가기 때문에 n + 1 을 합니다.
        int[] nums = new int[n + 1];
        
        // 반복문을 통해 첫번째 소수인 2부터 시작해서 n번 까지 빈 배열에 값을 넣어줍니다.
        for (int i = 2; i <= n; i++)
            nums[i] = i;

	// 반복문을 시작하는데, 숫자가 0일 경우 continue를 통해 다음값으로 넘어갑니다.
        // 즉, 0은 지워진 숫자로 가정하고 건너뛰는 용도입니다.
        for (int i = 2; i <= n; i++) {
            if (nums[i] == 0) continue;

		// 0이 아닐 경우 해당 수의 배수부터 출발하여 가능한 모든 숫자를 0으로(지웁니다) 바꿉니다.
            // 따라서 시작은 2 * i 가 되는것이고, j += i 를 통해 다음 배수값의 위치를 찾습니다.
            for (int j = 2 * i; j <= n; j += i) 
            	nums[j] = 0;
        }

	// 이제 0이 아닌 즉, 지워진 숫자가 아닌 소수만이 남은 값들을 출력해서 확인하면 됩니다.
        for (int i = 2; i <= 100; i++) {
            if (nums[i] != 0) {
                System.out.print(nums[i] + " ");
                answer++;
            }
        }
        System.out.println("\n" + answer);
        
	return answer;
    }

    public static void main(String[] args) {
        t solution = new t();
        solution.solution(100);
    }
}

 

위 처럼 소수들만을 찾아서 나온 값들을 확인할 수 있으며, 갯수 또한 확인이 가능합니다.

에라토스테네스의 체를 사용하면 효율적으로 소수를 찾을 수 있다는 것을 직접 코드를 작성하고 해보면서 겨우 이해할 수 있었습니다.

수포자인 저에게 이것조차도 처음엔 이해가 잘 안가는 듯 했는데, 역시나 직접 짜보니 이해하기가 무척 쉬웠습니다.

 

다만, 위의 코드에서 한가지 이해가 가지 않던 부분이 있었는데요.

이전 문제의 풀이에서 Math.sqrt 를 이용해서 받아온 값의 제곱근을 구해 해당 값의 크기만큼 반복문을 돌리는 부분이었습니다.

이게 어떻게 가능한지가 좀 이해가 가질 않아서 더 찾아본 결과 설명해놓은 글 중에 이 글이 제일 좋았던 것 같습니다.

설명은 아래와 같습니다.

 

 

 

 

n 이하의 모든 소수를 구한다고 가정합니다. 이 때, 해당 수 n은 자연수 a, b에 대해 n = a * b 라고 표현이 가능합니다.

예로, 12 는 2 * 6 혹은 3 * 4 등으로 나타낼 수 있다는 의미이며 a, b가 자연수라는 부분이 핵심입니다.

 

또 m = sqrt(n) 이라고 가정하면, n = m * m 이라고 할 수 있습니다.

여기서 sqrt는 square root로 제곱근을 의미합니다. 수식으로 표현하면 아래의 이미지와 같습니다.

n = a * b 이고, n = m * m 이라고 했으므로 a*b = m*m 이 됩니다. (a, b는 자연수이고 m은 n의 제곱근 입니다)

그렇다면 이 상태에서 a랑 b가 자연수가 되려면 다음의 세가지 경우 중 하나만 가능합니다.

• a = m 이고 b = m (n이 4와 같은 경우, m도 2처럼 자연수라면 가능합니다)
• a < m 이고 b > m
• a > m 이고 b < m

a, b가 자연수가 되려면 항상 위의 세가지 중 하나가 되며, 그렇다면 min(a ,b) <= m 인 것을 알 수 있습니다.

즉, a와 b중 작은 것은 m보다 작거나 같습니다.

 

n의 모든 약수에 해당하는 a와 b가 어떠한 약수이더라도 둘 중 하나는 반드시 m(=sqrt(n)) 이하 이므로, m 까지만 조사한다면 n이 소수인지 알 수 있게 됩니다.

 

그렇다면 이는 정확히 n에만 국한된 것이지, n 이하의 모든 수에 만족하지 않는다고 생각할 수 있습니다.

하지만 n보다 작은 것 중 가장 큰 수인 n -1 만 해도 sqrt(n) < sqrt(n - 1) 입니다.

즉, n보다 작은 수는 모두 sqrt(n) 내에 포함되므로 n뿐만 아니라 n미만의 모든 값에 대한 소수 판정이 가능해집니다.

 

제곱근에 관련한 내용은 아래의 블로그에서 그대로 가져왔습니다.

 

 

에라토스테네스 체에서 제곱근 관련한 내용을 설명한 블로그 입니다.

다만, 해당 글 링크는 왜인지 모르겠으나 안가져와 지기에 블로그 자체 링크를 가져왔습니다...

Nahwasa