[알고리즘] 소수 구하기(2) - 에라토스테네스의 체

아래는 소수 구하기(1)에서 했던 이야기의 요약입니다. (참고 : https://unounou.tistory.com/5)

 

<자연수 n이 소수인지 판별하는 방법>

2 이상 n-1 이하의 모든 정수로 나누었을 때 나누어 떨어지지 않는다. (1) ↓ 2 이상 n-1 이하의 모든 소수로 나누었을 때 나누어 떨어지지 않는다. (2)

 

7이 2로 나누어 떨어지지 않는다면, 2의 배수인 4와 6으로도 나누어 떨어지지 않습니다. 

 

7%2 7%3 7%4 → 불필요한 연산 7%5 7%6 → 불필요한 연산

방법(1)에서는 위의 나눗셈을 전부 했지만 이 중에는 불필요한 연산이 존재합니다. 7%4와 7%6입니다. 즉, 방법(1)에서 불필요한 연산을 제거한 것이 방법(2)입니다. 딱 봐도 그렇지만 방법(2)가 더 어렵습니다. 하지만 어려울 수록 차분히, 차근차근!

 

이 방법은 '에라토스테네스의 체'를 이용하였습니다.

 

아래 그림은 '에라토스테네스의 체'인데, 이 개념을 이용해서 에라토스테네스가 소수를 걸러내는 방법을 발명했습니다. 제 기억에는 중1 교육과정에 있었던 것 같네요.

우선 소수를 찾은 후에 표시하고, 소수의 배수들을 차례로 지워나가는 방법입니다. 끝까지 지워지지 않고 남아있는 것이 소수입니다. 이를 이용한 것이 방법(2)입니다.

 

에라토스테네스의 체

(출처 : 위키백과 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)

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

에라토스테네스의 체를 통해 소수를 구하는 건 빠르고 쉽지만 코드로 짜는 건 쉽지 않습니다. 

자바 코드를 살펴보도록 하겠습니다.

 

	public static void main(String[] args) {
		int cnt = 0; //나눗셈 횟수
		int primeCnt = 0; //찾은 소수의 개수(배열 인덱스 지정하기 위함)
		int[] prime = new int[250]; //소수 저장
		
		prime[primeCnt++] = 2;
		//prime[0]에 최초의 소수 2를 집어넣고, primeCnt값은 1이 된다.
        /*아래 for문에서 배열에 소수를 집어넣을 것이지만, n=3부터 실행할 것이기 때문에
        2는 for문에서 집어넣을 수 없다.
        따라서 for문에 들어가기 전에 prime[0]=2를 대입하고 반복문을 수행하는 것이다.
        */
		
		for(int n=3; n<=500; n+=2) { //3, 5, 7... 등 3 이상의 홀수 n에 대해서만 실행
			int i;
			for(i=1; i<primeCnt; i++) {
				cnt++; //나눗셈 실행할 것이므로 +1
				if(n%prime[i] == 0) break;
			}
			if(primeCnt == i) {
				prime[primeCnt++] = n;
			}
			
		}
		for(int i=0; i<primeCnt; i++) {
			System.out.println(prime[i]); //배열에 담긴 소수 출력
		}
		
		System.out.println("나눗셈 횟수 : " + cnt);
	}

 

<실행 결과>

2 3 5 ...(중략)... 491 499 나눗셈 횟수 : 4684

 

나눗셈 횟수가 현저히 줄어들었습니다! (방법(1)의 나눗셈 횟수 : 22279)

성능이 훨씬 좋아졌다는 것이 보입니다. 지금은 n의 값이 500이라서 실행 속도에 큰 차이는 안 나보입니다만, n의 값이 크면 클 수록 효율이 좋아지는 것을 체감할 수 있을 것입니다.

 

알고리즘에 대해 간단히 설명해 보겠습니다.

 

n을 2 이상 n-1 이하의 소수로 나누기 위해서는, 소수를 저장하는 배열이 필요합니다. 소수를 찾아서 int[] prime 배열에 차곡차곡 집어넣습니다. 배열의 크기가 250인 이유는 500개의 자연수 중에서 홀수의 개수가 250개이기 때문입니다. 왜 홀수의 개수를 생각할까요? 그 이유는, 2는 최초의 소수이면서 동시에 유일한 짝수인 소수이기 때문입니다. 4, 6, 8... 등 나머지 짝수는 소수가 아닙니다. 따라서 2 이상의 짝수는 절대로 배열에 들어갈 후보가 될 수 없습니다. 재미있지 않나요? ㅎㅎ

반복문에 들어가기 전에 배열에 2를 저장한 이유는 그 때문입니다. 반복문에서는 3 이상의 홀수만 소수의 후보로서 판단할 것이기 때문에 prime[0]에 미리 2를 저장한 수에 반복문을 수행합니다.

 

prime[0]에 2가 담겼지만 i값이 0이 아닌 1부터 나눗셈을 하는 이유는, n은 홀수이기 때문에 n%2==0이 될 수가 없기 때문입니다. 물론 i값을 0부터 해도 소수 구하는 데에 문제는 없겠습니다만 성능에는 더 좋지 않을 것입니다. 따라서 prime[0]이 아닌, prime[1]부터 나눗셈을 수행합니다. (prime[0]==2, prime[1]==3입니다.)

 

나누어 떨어지는 순간이 생기면 break문을 만나 반복문이 종료되고, n값에 +2를 해서 다른 홀수에 대해서 판단을 시작합니다. 나누어 떨어지지 않으면 break문을 만나지 않고 소수인 것이 판별됩니다. if문을 만나 prime 배열에 해당 소수를 집어넣게 됩니다. 그 후 primeCnt++ 후위 연산을 수행하여 primeCnt 값이 +1 됩니다. 그래야 배열의 인덱스 번호가 하나 증가하고 그 후 배열에 값을 대입할 수 있게 됩니다.

 

이해가 잘 안 되면 꼭 종이에 써서 확인해 보시길 바랍니다.

 

방법(1)보다는 방법(2)가 효율이 좋지만, 빠른 알고리즘이라고 해서 모든 점이 다 좋은 것은 아닙니다. 이 방법의 경우 배열에 소수를 할당해야 하기 때문에, 많은 메모리를 요구합니다.

 

다음 포스팅에서는 이를 개선한 다른 알고리즘을 소개하도록 하겠습니다.

 

---

Do it! 자료구조와 함께 배우는 알고리즘 입문 자바 편을 읽고 정리한 게시글입니다.

책의 개념을 바탕으로 생각을 추가하여 작성하였습니다.