소수

주빈·2022년 2월 9일

Java algorithm

algorithm

목록 보기

2/16

오늘은 소수에 대해 알아보자.

📘 소수란?

자신과 1 이외의 정수로 나누어 떨어지지 않는 정수다.

그러므로 어떤 정수 n에 대하여 2부터 n - 1까지의 어떤 정수로도 나누어 떨어지지 않는 수를 의미한다. 만약 나누어 떨어지는 정수가 하나 이상 존재하게 되면 그 수는 '합성어' 라고 한다.

✏ 소수 판별 코드

소수를 판별하는 코드를 작성해보자 일단 2부터 1000까지의 정수 중 소수를 판별하여 출력하는 코드를 작성해보았다.

public class Main {
    public static 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);
        }
    }
}

안쪽 for문을 보면 알 수 있지만 for문의 반복이 종료된 시점에서 변수의 i값은

(1) n이 소수인 경우 : n과 같은 값 (for문이 끝까지 실행된다.)
(2) n이 합성수인 경우 : n보다 작은 값 (for문이 중단된다.)

라는 것을 알 수 있다.

또한 코드를 실행하면 for문에 의해 소수를 찾기 위해서 나눗셈을 실행한 횟수(counter)가 78022가 되는 것을 알 수 있다.

✏ 알고리즘 개선 (1)

예를 들어 어떤 정수 n이 2또는 3으로 나누어 떨어지지 않는다면 2X2인 4 또는 2X3인 6으로도 나누어 떨어지지 않는다. 그러므로 불필요한 나눗셈을 줄여서 코드를 작성하면 알고리즘 개선이 될 것이다.

public class Main {
    public static void main(String[] args) {
        int counter = 0;    // 나눗셈 횟수
        int pointer = 0;    // 찾은 소수의 개수
        int[] findNum = new int[500];   // 찾은 소수를 저장하는 배열

        findNum[pointer++] = 2;     // 2는 소수이기 때문에 미리 저장

        for (int n = 3; n <= 1000; n += 2) {    // 나누는 수는 홀수만
            int i ;
            for (i = 1; i < pointer; i++) {     // 이미 찾은 소수로 나누어 보기
                counter++;
                if (n % findNum[i] == 0)    //나누어 떨어지면 소수가 아님
                    break;
            }
            if (pointer == i)   // 마지막까지 나누어 떨어지지 않으면
                findNum[pointer++] = n;     // 소수라 배열에 저장
        }
        for (int i = 0; i < pointer; i++)
            System.out.println(findNum[i]);

        System.out.println(counter);
    }
}

위의 코드에서 홀수로만 나누는 이유는 4 이상의 짝수는 2로 나누어 떨어지므로 소수가 아니기 때문이다. 이 코드를 실행하면 나눗셈을 수행한 횟수는 14622로 현저히 횟수가 줄어든 것을 알 수 있다.

✏ 알고리즘 개선 (2)

100의 약수를 한번 알아보자

(1) 2 X 50
(2) 4 X 25
(3) 5 X 20
(4) 10 X 10
(5) 20 X 5
(6) 25 X 4
(7) 50 X 2

이렇듯 7개가 있지만 (4)번을 제외하고는 대칭을 이루어 앞뒤 순서만 다르지 같은 수라는 것을 알 수 있다. 이는 (4)번 까지만 나눗셈을 실행하고 (5) ~ (7)번의 나눗셈은 실행하지 않아도 그 과정에서 한 번도 나누어 떨어지지 않는다면 소수라고 판단해도 좋다.

즉, 어떤 정수 n에 대하여 "n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다." 라고 판단할 수 있다. 이것을 이용하여 알고리즘을 한 번더 개선해보자.

public class Main {
    public static void main(String[] args) {
        int counter = 0;    // 나눗셈 횟수
        int pointer = 0;    // 찾은 소수의 개수
        int[] findNum = new int[500];   // 찾은 소수를 저장하는 배열

        findNum[pointer++] = 2;     // 2는 소수이기 때문에 미리 저장
        findNum[pointer++] = 3;		// 3도 소수기 때문에 미리 저장

        for (int n = 5; n <= 1000; n += 2) {    // 나누는 수는 홀수만
            boolean flag = false;
            for (int i = 1; findNum[i] * findNum[i] <= n; i++) {
                counter += 2;
                if (n % findNum[i] == 0) {      // 나누어 떨어지면 소수가 아님
                    flag = true;
                    break;
                }
            }
            if (!flag) {    // 마지막까지 나누어 떨어지지 않으면
                findNum[pointer++] = n;     // 소수라 배열에 저장
                counter++;
            }
        }
        for (int i = 0; i < pointer; i++)
            System.out.println(findNum[i]);

        System.out.println(counter);
    }
}