[자료구조와 알고리즘] 소수 구하기

 

어떤 정수 이하의 소수를 모두 나열하는 알고리즘입니다.

소수의 정의부터 살펴보자면 자신, 1외의 정수로 나누어 떨어지지 않는 정수입니다.

public class PrimeNumber {
    public static void main(String[] args) {
        int counter = 0; //나눗셈 횟수 측정

        for(int n = 2; n <= 1000; n++) { //2부터 1000까지의 정수 범위
            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);
    }
}

이러한 방식으로 어떤 정수 n이 있을 때 정수 범위 -1까지 나눗셈을 진행하여 소수인지 아닌지 판단해볼 수 있습니다.

---

여기서 소수를 구하는 알고리즘을 개선해볼 수 있는데 소수를 어떤 방법으로 구할 수 있는지, 더 적은 계산 횟수로 소수를 구할 수 있는 방법이 있는지 살펴보겠습니다.

1.n이 2 또는 3으로 나누어 떨어지지 않으면 2의 배수 4, 6으로도 나누어 떨어지지 않습니다. 즉 정수 n이 소수인지의 여부는 2부터 n-1까지의 어떤 소수로도 나누어 떨어지지 않는지의 조건만 확인하면 됩니다. 예를 들어 11같은 경우 11보다 작은 소수 2,3,5,7로만 나눗셈을 해도 충분합니다.

2. 어떤 정수 n이 소수인지 확인하려면, n의 제곱근 이하의 소수로 나누어떨어지는지 확인하면 충분합니다. 만약 n이 소수가 아니라면, 적어도 하나의 소인수 p가 존재하고, 이때 p * q = n을 만족합니다.

• 최소 하나의 인수 p는 sqrt(n) 이하입니다. (그렇지 않으면 두 인수 모두 sqrt(n)보다 커야 하고, 그 경우 p * q > n이 되어 모순)
• 따라서, sqrt(n) 이하의 소수만 검사하면 소수 여부를 판별할 수 있습니다

 

예를 들어 65의 경우 제곱근 이하의 소수 5로 이미 나누어 떨어지고, 5*13, 13*5는 계산이 중복되기 때문에 제곱근 이상의 소수로 검사할 필요가 없어지는 것입니다.

public class PrimeNumber2 {
    public static void main(String[] args) {
        int counter = 0; //횟수 측정
        int ptr = 0; //소수의 갯수
        int[] prime = new int[500];

        prime[ptr++] = 2; //2와 3은 모두 소수이므로 배열에 저장
        prime[ptr++] = 3;
        for(int n = 5; n <= 1000; n+=2) {
            boolean flag = false;
            for(int i = 1; prime[i]*prime[i] <= n; i++) { //제곱근 이하의 범위
                counter+=2;
                if(n % prime[i] == 0) {
                    flag = true;
                    break;
                }
            }
            if(!flag) {
                prime[ptr++] = n; //소수를 배열에 저장
                counter++;
            }
        }
        for(int i = 0; i < ptr; i++)
            System.out.println(prime[i]);
        System.out.println("나눗셈을 수행한 횟수 : "+counter);
    }
}

두 코드의 결과를 비교해보겠습니다. 계산 횟수가 개선된 알고리즘을 적용했을 때 훨씬 줄어들은 것을 확인해볼 수 있습니다.