[알고리즘] 소수 구하기(1)

자연수(=양의 정수)는 세 가지로 나누어 집니다.

1, 소수, 그리고 합성수입니다.

소수란, 1과 자기 자신을 제외한 어떤 정수로도 나누어 떨어지지 않는 정수를 뜻합니다. 1과 소수를 제외한 모든 자연수는 합성수에 속합니다. 예를 들어 7의 약수는 1과 7 뿐이므로 소수이고, 6의 약수는 1, 2, 3, 6이므로 합성수입니다. 어떤 자연수가 소수인지 아닌지 판별하기 위해서는 해당 숫자의 약수를 생각해 보면 된다는 뜻입니다. 약수의 개념은 초등학교 때 처음 배워 계속 써먹기 때문에 머리로는 금방 판단할 수 있지만 수가 조금만 커지면 힘들어집니다. 2, 3, 5, 7, 11, 13...까지는 금방이지만, 479가 소수인지 판단하려면 어떨까요? 이를 판단하기 위해서는 알고리즘을 생각해 봐야 합니다.

 

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

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

이를 바탕으로 자바에서 소수를 나열하는 프로그램을 만들어보겠습니다.

 

	public static void main(String[] args) {
		int cnt = 0; //나눗셈 횟수
		int i;
		
		for(int n=2; n<=500; n++) {
        //2 이상 500 이하의 소수를 나열할 것
			for(i=2; i<n; i++) {
				cnt++; //나눗셈 할 때마다 +1
				if(n%i == 0) { //해당 수를 i로 나눈 나머지가 0이면 소수가 아니다
					break; 
                    //반복문 종료하고 바깥쪽 반복문으로 가서 n++ 수행. 
                    //해당 숫자는 소수가 아니고 그 다음 숫자 판단 시작.
				}
			}
			if(n == i) { 
            //안쪽 반복문이 종료되지 않고 해당 행까지 와서 n==i가 되면 소수라는 뜻
				System.out.println(n);
			}
		}
		System.out.println("나눗셈 횟수 : " + cnt);
	}

 

<실행 결과>

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

 

이해를 돕기 위해 예시를 통해 알아보도록 하겠습니다. 6이 소수인지 알아보기 위해서 수행하는 나눗셈은 다음과 같습니다.

 

6%2  6%3 6%4 6%5

하지만 실제로 이 계산을 전부 수행하지는 않습니다. 6%2==0이기 때문에 나눗셈은 즉시 종료됩니다. n%i==0이 되면 break문을 통해 반복문은 종료되고, 해당 수는 소수가 아니기 때문에 출력하지 않습니다.

 

7이 소수인지 판별하는 나눗셈을 나열해 보겠습니다.

7%2 7%3 7%4 7%5 7%6

해당 연산 중에 결과값이 0이 되는 경우는 발생하지 않습니다. 다시 말해, n%i==0가 성립하는 경우는 없습니다. 따라서 break문을 만나지 않고 그 다음 if문으로 넘어가서, n==i가 성립하기 때문에 n값인 7을 출력하게 됩니다. 즉, 7은 소수입니다.

 

n값을 500까지 시행하게 되면 나눗셈 횟수는 총 22279번이 됩니다. 사람이 저 나눗셈을 손으로 하면 하루는 족히 걸리겠네요. 하지만 컴퓨터는 순식간에 연산이 가능합니다. 느린 저의 노트북도 금방 연산을 해내네요.

하지만 성능이 좋은 연산이라고 보기는 어렵습니다. 이왕이면 같은 시간에 더 많은 일을 해내는 것이 효율이 좋으니까요. 

 

어떻게 하면 성능을 개선할 수 있을까요? 다시 한 번 7을 예시로 삼아보겠습니다.

7이 2로 나누어 떨어지지 않는다면, 2의 배수인 4와 6으로도 나누어 떨어지지 않습니다. 조금만 생각해 보면 당연한 말이라는 것을 알 수 있습니다.

다시 말해,

7%2 7%3 7%4 7%5 7%6

7%4와 7%6은 필요없는 연산입니다. 모든 자연수에 대해서 이러한 불필요한 연산을 줄이면 성능이 개선될 것입니다. 모든 자연수로 나눌 필요가 없고, 소수로 나누었을 때 나누어 떨어지지만 않는다면 소수의 배수인 합성수로 나누었을 때도 나누어 떨어지지 않을 것임이 자명합니다.

 

결론입니다.

 

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

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

 

개선된 알고리즘은 다음 포스팅에 계속 이어서 설명하도록 하겠습니다.

 

처음 소수 구하기를 배울 때는 혼자 코드를 짜보다가 잘 안 돼서 씩씩 거리면서 구글링 해보던 기억이 나는데, 지금 다시 보니 별로 어렵지 않네요.

역시 무언가를 습득할 때는 지식 숙성의 시간이 필요하다는 것을 다시 한 번 느낍니다. 반복만이 살 길!

 

---

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

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