소수 나열하기

소수 나열하기

 

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

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

예를 들어 13은 2, 3, ..., 12 가운데 어떤 정수로도 나누어 떨어지지 않습니다.

그러므로 어떤 정수 n이 다음의 조건을 만족하면 소수임을 알 수 있습니다.

2부터 n - 1 까지의 어떤 정수로도 나누어 떨어지지 않습니다.

만약 나누어 떨어지는 정수가 하나 이상 존재하면 그 수는 합성수(composite number)입니다.

 

다음은 1,000 이하의 소수를 나열하는 프로그램입니다.

 

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

class PrimeNumber1 {
    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);
        }

        System.out.println("나눗셈을 수행한 횟수 : " + counter);
    }
}

 

개선 버전 (짝수는 2로 나눠지므로 합성수이고 홀수중에 소수로 나눠지면 소수 배열에 추가 다시 소수배열값으로 비교)

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

class PrimeNumber2 {
    public static void main(String[] args) {
        int counter = 0;                                // 나눗셈 횟수
        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]);

        System.out.println("나눗셈을 수행한 횟수 : " + counter);
    }
}

 

100의 약수

2 * 50

4 * 25

5 * 20

10 * 10

20 * 5

25 * 4

50 * 2

 

즉 어떤 정수 n은 다음 조건을 만족하면 소수라고 판단할 수 있다.

n의 제곱근 이하의 어떤 소수로도 나누어떨어지지 않습니다.

위 조건을 바탕으로 다시 개선한 버전

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

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

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

        System.out.println("곱셈과 나눗셈을 수행한 횟수: " + counter);
    }
}