[알고리즘]효율적인 소수 선별

재키·2020년 3월 22일
0

알고리즘

목록 보기
2/4

본 글은 Bohyoh Shibata의 "자료구조와 함께 배우는 알고리즘 입문(자바편)"을 참고하여 작성하였습니다.

소수 선별 문제의 본질

특정 범위내의 소수를 선별하는 문제는 선별 대상 미만의 수로 해당 수를 나누는 방식으로 해결할 수 있다. 가령 100이하의 범위에서 소수를 선별하기 위해 2 이상 100이하인 수 x를 2 이상 x 미만의 수로 나누어본다. 만약 어떤 수로도 나누어지지 않는다면 x는 소수다. 그렇다면 약간의 사고를 더하여 나누는 수를 미리 거를 수 있다면 나눗셈의 횟수를 줄일 수 있지 않을까?

일반적인 소수 선별 알고리즘

1) 알고리즘
1000이하의 소수를 선별하기 위해 2이상 검증하려는 수 미만의 모든 수로 나누어보는 것이다. 반복문을 통해 나누는 횟수를 구해보도록 하자.

2) 코드

class PrimeNumber1 {
	public void main(String[] args) {
    	int counter = 0; // 나눗셈의 횟수
        
        for (int n = 2; n <= 1000; n++) {
        	int i;
            for (i = 2; i < n; i++) {
            	counter++;
                if (n % i == 0) break; // 나누어떨어지면 소수가 아님
            }
 	    if (n == i) { // 마지막까지 나누어떨어지지 않음 
            	System.out.println(n);
            }
            
        }
        System.out.println('나눗셈을 수행한 횟수: ' + counter);
    }
}

3) 결과

1000이하의 소수를 선별하기 위해 8만번의 가까운 나눗셈을 수행하였다.

나눗셈 횟수를 줄이기 위한 방법1: 소수로만 나누는 방법

1) 알고리즘
소수인지를 판별하는 수 미만의 소수로 해당 수를 나눠보는 방법이다. 모든 합성수는 소수의 곱으로 치환될 수 있기 때문에 모든 소수로 나눠떨어지지 않는다면 합성수로 나눠떨어지지 않는다. 따라서 소수로 판별된 수를 저장하는 공간을 생성하여 판별과정을 통과한 수를 저장하며 차례로 검증한다.

2) 코드

class PrimeNumber2 {
	public void main(String[] args) {
    	int counter = 0; // 나눗셈 횟수
        int ptr = 0; // 찾은 소수의 개수
        int[] prime = new int[500] // 소수를 저장하는 공간(배열)
        
        prime[ptr++] = 2;
        
        for (int n = 3; n <= 1000; n += 2) { // 2가 소수이므로 짝수는 배제한다
            int i; // prime 배열의 인덱스
            for (i = 1; i < ptr; i++) {
            	counter++;
                if (n % prime[i] == 0) break;
            }
            if (ptr == i) prime[ptr++] == n;
        }
        
        for (int i = 0; i < ptr; i++) {
        	System.out.println(prime[i]);
        }
        
        System.out.println("나눗셈을 수행한 횟수: " + counter);
    }
}

위의 코드 중 두 번째 for문의 초기값(i)이 1인 것이 의문이다. 프로세스를 잘 따라가보자. 처음 n = 3일때, ptr은 1이다. 따라서 안쪽의 for문은 실행되지 않는다. 이어지는 if문에서 ptr == i이므로 3을 prime[1]에 넣어준다. 이 프로세스 안에는 짝수가 소수가 아니라는 점(2인 prime[0]을 배제한 것)과 3은 소수라는 기본 지식이 녹아있는 듯 하다. 실제로 초기값이 0인 경우와 1인 경우를 비교하면 다음과 같다.
(1) 0인 경우

(2) 1인 경우

나눗셈 횟수를 줄이기 위한 방법2: n의 제곱근 이하의 소수로 나누는 방법

1) 알고리즘
100의 약수는 다음과 같이 나타낼 수 있다(단, 1x100과 100x1은 제외한다).
2x50, 4x25, 5x20, 10x10, 20x5, 25x4, 50x2

약수를 나타내는 방법을 살펴보면 10x10을 기준으로 대칭의 형태를 이룬다. 만약, 100이 2로 나누어떨어지지 않는다고 한다면 100이 50으로 나누어떨어지지 않는다(실제론 이렇지 않다). 따라서 특정 수(n)가 소수인지를 판별하기 위해서는 n의 제곱근 이하의 소수로만 나누어떨어지는지만 판별하면 된다.

2) 코드

class PrimeNumber3 {
	public static void main(String[] args) {
    	int counter = 0;
        int ptr = 0;
        int[] prime = new int[500];
        
        prime[ptr++] = 2; // 2는 소수다.
        prime[ptr++] = 3; // 3도 소수다.
        
        for (int n = 5; n <= 1000; n += 2) {
            boolean flag = false;
            for (int i = 1; prime[i]*prime[i] <= n; i++) { // -----(1)
            	counter += 2;
                if (n % prime[i] == 0) {
                    flag == true;
                    break;
                }
            }
            if (!flag) {
            	primt[ptr++] = n;
                couter++; // -----(2)
            }
        }
  		
        for (int i = 0; i < ptr; i++) {
            System.out.println(prime[i]);
        }
        
        System.out.println("곱셈과 나눗셈을 수행한 횟수: " + counter);
    }
}

flag는 n이 n의 제곱근 이하의 수로 나누어 떨어지면 true, 그렇지 않다면 false를 저장하는 boolean형 변수이다.
여기서 counter를 계산하는 프로세스가 와닿지 않는다. 이를 찬찬히 살펴보자. (1)에서 prime[i]Xprime[i] <= n 인지 판별하기 위해 한 번의 곱셈이, n이 prime[i]로 나누어 떨어지는 지 판별하기 위해 한 번의 나눗셈이 수행되었기 때문에 counter += 2가 올바르다.
그 다음 (2)에서 prime[i]Xprime[i] <= n을 판별하기 위해 한 번의 곱셈이 수행되었으나 prime[i]Xprime[i] > n이면 for문이 수행되지 않으므로 counter += 2가 수행되지 않는다. 이 경우, 나눗셈을 수행할 필요가 없기 때문에 counter += 2를 수행하는 것이 올바르지 않다. 결국, 판별 이후에 그것을 조정해준다.

3) 결과

결론

알고리즘을 개선한 결과, 약 8만의 수행과정이 약 4천의 수행과정으로 크게 줄어들었다. 물론, 소수를 저장하는 공간이 필요하기 때문에 공간 효율은 떨어졌을지라도 수행과정을 큰 폭으로 줄였다는 것이 놀랍다. 작은 단서가 알고리즘의 효율에 크게 기여할 수 있네...

profile
기초를 탄탄히!

0개의 댓글