소수 나열하기

📃 1 이상 1000 이하의 소수를 나열하는 프로그램 작성해보기

소수는 자신과 1 이외의 어떤 정수로도 나누어떨어지지 않는 정수이다.
2부터 n-1까지의 어떤 정수로도 나누어떨어지지 않는다.

class PrimeNumber1 {
    public static void main(String[] args) {
        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문의 반복이 종료된 시점에서 변수 i값은 다음과 같다.

• n이 소수인 경우 : n과 같은 값
• n이 합성수인 경우 (소수가 아닌 경우) : n보다 작은 값

📉 코드 개선 1

하지만 위에 코드는 불필요한 연산이 많기 때문에 조금 더 개선해서 작성해보자.
정수 n이 소수인지의 여부는 어떤 소수로도 나누어떨어지지 않는다는 조건을 만족시키면 된다.
이를 바탕으로 전체 숫자를 하나씩 나누는게 아닌 소수로 나누어보면 좀 더 효율적으로 작성할 수 있다.

소수를 구하는 과정에서 그 때까지 구한 소수를 배열 prime의 요소로 저장한다.
n이 소수인지를 판단하기 위해서 배열 prime에 저장되어 있는 요소들로 나눗셈을 진행하고 나누어떨어지지 않으면 prime 배열의 요소를 추가해준다.
짝수인 값은 2로 나누어떨어지므로 소수가 아니기 때문에 증가값은 1이 아닌 2로 설정하여 홀수만 판단할 수 있도록 한다.

// 1,000 이하의 소수를 나열(버전 2)

class PrimeNumber2 {
    public static void main(String[] args) {
        int ptr = 0;                                    // 찾은 소수의 개수
        int[] prime = new int[500];                     // 소수를 저장하는 배열

        prime[ptr++] = 2;                               // 2는 소수임

        for (int n = 3; n <= 1000; n += 2) {            // 조사 대상은 홀수만
            int i;
            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++)                   // 찾은 ptr개의 소수를 출력
            System.out.println(prime[i]);

    }
}

📉 코드 개선 2

어떤 값의 약수를 구할 때 그 값의 반까지의 나눗셈만 수행하면 약수를 구할 수 있다.
이를 바탕으로 계산량을 줄여 코드를 개선할 수 있다.
즉, 어떤 정수 n은 다음 조건을 만족하면 소수라고 판단할 수 있다.

n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않는다.
prime[i]의 제곱이 n 이하인가?

이때 제곱근을 구하지 않고 곱셈을 사용하여 제곱을 구한다. n의 제곱근을 구하는 것보다 제곱을 구하는 것이 훨씬 간단하고 빠르기 때문이다.

// 1,000 이하의 소수를 나열(버전 3）

class PrimeNumber3 {
    public static void main(String[] args) {
        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++) {
                if (n % prime[i] == 0) {        // 나누어떨어지면 소수가 아님
                    flag = true;
                    break;                      // 더 이상 반복은 불필요
                }
            }
            if (!flag) {                       // 마지막까지 나누어떨어지지 않음
                prime[ptr++] = n;              // 소수로 배열에 저장
            }
        }

        for (int i = 0; i < ptr; i++)        // 찾은 ptr개의 소수를 출력
            System.out.println(prime[i]);
    }
}