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

앞서 소수 구하는 알고리즘을 두 가지 알아보았습니다. 이들을 개선한 세 번째 방법에 대해 알아보겠습니다. 사실 좀 어렵습니다. 정신을 바짝 차리고... 시작합니다.

 

두 번째 방법을 다시 한번 살펴보겠습니다.

 

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

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

 

이 방법을 어떻게 개선할 수 있을까요? 나눗셈의 횟수를 줄이면 됩니다. 이미 한 차례 나눗셈의 횟수를 줄였는데, 어떻게 하면 다시 줄일 수 있을지 생각해 보겠습니다.

 

이쯤에서 다시 한 번 상기해야 할 것은, 소수 구하기의 본질은 '약수 구하기'라는 것입니다. 프로그램 상에서는 n%i==0이 성립할 때 i는 n의 약수라고 판단합니다. 

약수 구하기를 하면서 이러한 방법을 사용해 본 적이 있을 것입니다. 100을 예시로 들어보겠습니다.

 

1 x 100 (불필요하므로 제외하고 생각) 2 x 50 4 x 25 5 x 20 10 x 10 20 x 5 25 x 4 50 x 2 100 x 1 (불필요하므로 제외하고 생각)

 

왼쪽 숫자인 1, 2, 4, 5, 10, 20, 25, 50, 100이 100의 약수입니다. 여기서 1 x 100이 불필요한 이유는, n%i 연산에서 i값에 1과 자기 자신(n)은 대입하지 않기 때문입니다. 주목해야 하는 것은, 가운데 10 x 10을 대칭으로 같은 연산이 반복된다는 것입니다. 10 x 10 이후로는 몫과 나누는 수가 대칭으로 반복되기 때문에 같은 연산을 두 번 할 필요는 없습니다. 여기서 10은 100의 제곱근, 즉 루트 100입니다. 루트 n을 기준으로 같은 연산이 대칭됩니다. 이를 이용해서 계산량을 줄일 수 있습니다. 10 x 10 이전의 소수로만 나눗셈을 수행한 후 나누어 떨어지지 않으면 소수라고 판단할 수 있습니다.

 

결론입니다.

 

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

제곱근 n(루트 n) 이하의 모든 소수로 나누었을 때 나누어 떨어지지 않는다.

 

예를 들어, 29가 소수인지 판단해 보겠습니다.

이전 알고리즘인 방법(2)를 사용했을 때 수행해야 하는 나눗셈은 다음과 같습니다.

 

29%2 29%3 29%5 29%7 29%11 29%13 29%17 29%19 29%23

해당 연산의 값은 전부 0이 아니므로 29는 소수입니다. 총 9번의 나눗셈 수행을 하였습니다. 이를 개선한 방법 3을 사용하면 어떨까요? 방법 3의 핵심은 제곱근 29, 즉 √29를 사용하는 것입니다. √29=5.xx이므로 그 이하의 소수로만 나누어 보면 됩니다. 다시 말해서, 5 이하의 소수로만 나누면 된다는 뜻입니다.

 

29%2 29%3 29%5

이 연산만 해보면 됩니다. 해당 연산의 값은 전부 0이 아니므로 29는 소수입니다. 총 3번의 나눗셈을 수행하였습니다. 나눗셈 횟수가 훨씬 줄어든 것을 볼 수 있습니다. 신기하지 않나요?

 

여기까지만 설명하면 신기하긴 하지만 사실 무슨 말인지 잘 이해가 안 됩니다. 저 역시 공리처럼 알고 있는 것을 막상 설명하려고 하니 어렵더라구요. 다른 예시들을 조금 더 보겠습니다.

(해당 블로그의 아이디어를 참고하여 작성하였습니다.

https://m.blog.naver.com/PostView.nhn?blogId=pooong_story&logNo=70152320103&proxyReferer=https:%2F%2Fwww.google.com%2F)

 

 

29÷2=14.5 29÷3=9.66... 29÷4=7.25 29÷5=5.8 29÷7=4.14... 29÷9=3.22... 29÷14=2.07...

 

여기서 나누는 수와 몫의 정수 부분을 보면 2와 14, 3와 9, 4와 7... 이런 식으로 나열할 수 있습니다. √29=5.xx이고 나누는 수가 5 이상이라면 몫의 정수 부분은 5 이하가 됩니다. 5 이하의 정수로만 나누어 보아도, 나누는 수와 몫의 정수 부분은 무조건 하나가 5 이상이면 나머지 하나는 5 이하이기 때문에 반복되는 연산을 줄일 수 있습니다.

 

(방법(2)를 개선한 방법이므로 사실상 4, 9, 14로 나누는 것도 필요없는 연산이 되지만 설명을 위해 덧붙였습니다.)

 

더 구구절절 쓰면 프로그래밍 알고리즘이 아닌 수학 수업이 되므로 여기까지만 적겠습니다. 저 역시 증명은 무리입니다. 그냥 받아들일 뿐입니다. (ㅎㅎ)

 

이제 자바 코드를 살펴보겠습니다.

 

	public static void main(String[] args) {
		int cnt = 0; //나눗셈 횟수
		int primeCnt = 0; //찾은 소수의 개수
		int[] prime = new int[500]; //소수 저장

		prime[primeCnt++] = 2;
		prime[primeCnt++] = 3;
		//반복문에 들어가기 전에 prime[0]=2, prime[1]=3 배열에 넣고 시작
		
		for(int n=5; n<=500; n+=2) {
		//prime 배열에 소수 2와 3이 이미 들어있으므로 n=5부터 시작
			boolean tmp = false;
			for(int i=1; prime[i]*prime[i] <= n; i++) {
				cnt += 2;
				/*두 가지 연산을 수행하므로 cnt는 +2
				 prime[i]*prime[i] <= n과 n%prime[i]
				 */
				
				if(n % prime[i] == 0) {
					tmp = true;
					break;
				}
			}
			
			if(!tmp) {
				prime[primeCnt++] = n;
				cnt++;
			}
		}
		
		for(int i=0; i<primeCnt; i++) {
			System.out.println(prime[i]); //배열에 담긴 소수 출력
		}
		
		System.out.println("곱셈과 나눗셈 횟수 : " + cnt);
	}

 

<실행 결과>

2 3 5 7 ...(중략)... 491 499 곱셈과 나눗셈 횟수 : 1589

 

prime[i]*prime[i]<=n을 사용해도 되고, prime[i]<=Math.sqrt(n)을 사용해도 됩니다. 결과는 같습니다. sqrt(n)를 사용하여 제곱근을 구하면 실수 계산이 들어가므로 제곱을 구하는 게 더 빠릅니다.

 

곱셈과 나눗셈 횟수가 줄어들어 효율이 좋아진 것을 확인할 수 있습니다.

(방법(2)의 나눗셈 횟수 : 4684 / 방법(1)의 나눗셈 횟수 : 22279)

 

방법 (2)와 비슷하므로 자세한 설명은 생략합니다. 2와 3을 미리 배열에 넣어두고 5 이상의 소수를 판단한다는 것만 염두에 두시면 크게 다른 점은 없습니다.

 

이상 소수 구하기 알고리즘을 마무리하도록 하겠습니다.

 

정처기 준비할 때 가장 애먹었던 코딩 문제 중 하나입니다. 손으로 몇번이나 써봤지만 이상하게 자꾸 틀린 답이 나오더라구요. 책에서는 다른 코드로 나와있었지만, 둘 다 어렵습니다...

---

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

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