P-coding

이번 글에서는 백준 17103번 문제를 통해 소수 찾기 알고리즘인 에라토스테네스의 체를 활용,
이를 통해 소수를 찾고 짝수를 소수의 합으로 나타내보자.

---

문제 핵심

• N : 짝수
  • 2 < N <= 1,000,000
• 두 개의 소수의 합이다.
• 순서만 다른 것은 같은 파티션이다.

풀이 과정

다음 문제는 소수를 먼저 찾아서 합을 구하면된다.

즉, 에라토스테네스의 체를 활용 소수를 효율적으로 구할 수 있다.

1. 소수 찾기

먼저 소수를 분별한다. ( max값을 찾아서 할 수 있지만 최대값 1,000,000인 점을 감안 미리 1,000,000까지 소수를 찾는다. )

    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (!isPrime[i]) continue;
            for (int j = i + i; j <= num; j += i) {
                isPrime[j] = false;
            }
        }
    }

2. 골드 바흐 파티션 구성

1. 양쪽에서 숫자를 줄여가며 소수 체크를 한다. ( 이 때 양쪽에서 검사하기 때문에 절반만 사용한다. )

2. 둘 다 소수일 때 count를 증가시킨다.

3. count를 반환한다.

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }

미리 찾아둔 소수를 활용하고 반복문을 효율적으로 사용하면 비교적 쉬운 문제이다.
1,000,000 이하의 소수는 미리 생성해도 처리 가능하지만,
숫자가 매우 커질 경우에는 입력값의 최대값을 기준으로 소수를 구하는 것이 더 효율적이다.

이번 문제는 두 수의 합이 N이 되어야 하므로, 다음과 같은 방식이 적합하다.다만, 이전에 선택 정렬 문제에서 사용한 인덱스를 활용한 방식으로 데이터를 저장하는 방법도 고려할 수 있다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    private static boolean[] isPrime;

    public static void main(String[] args) throws IOException {
        solve();
    }

    private static void solve() throws IOException {

        sieveOfEratosthenes(1000000);

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int N = Integer.parseInt(bufferedReader.readLine());

        for(int i = 0;i<N;i++){
            int num = Integer.parseInt(bufferedReader.readLine());
            String result = String.valueOf(findGBPartitions(num));
            stringBuilder.append(result)
                    .append("\n");
        }

        System.out.println(stringBuilder);
    }


    private static void sieveOfEratosthenes(int num) {
        isPrime = new boolean[num + 1];

        for (int i = 2; i <= num; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (!isPrime[i]) continue;
            for (int j = i + i; j <= num; j += i) {
                isPrime[j] = false;
            }
        }
    }

    private static int findGBPartitions(int evenNum) {
        if(evenNum < 4 || evenNum % 2 != 0) {
            throw new IllegalArgumentException(" 4이상의 짝수만 입력 가능합니다. ");
        }

        int count = 0;

        for (int i = 2; i <= evenNum / 2; i++) {
            if(isPrime[i] && isPrime[evenNum - i]) {
                count++;
            }
        }
        return count;
    }
}

에라토스테네스의 체 는 소수를 찾는 쉽고 빠르게 찾을 수 있는 방법이다.

( 고대 그리수 수학자 에라토스테네스가 발견 )

알고리즘

다음과 같은 알고리즘을 따른다.

0 ~ 50 까지의 수를 찾고자 할때, 0과 1을 제외

1.  2부터 시작하여 2를 제외한 2의 배수를 모두 지운다.

2. 지워지지 않은 다음 숫자부터 1번과 같이 반복한다. ( 3을 제외한 3의 배수 지우기 )

3.  √50 = 7.071 이므로 구하는 수의 제곱근 이하의 소수, 즉, 7의 배수까지 제외하면 된다.

4. 제외 되지 않은 숫자가 소수

 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Code

자바를 통해 다음과 같이 구현할 수 있다.

Boolean[] primeNumbers = new Boolean[number + 1]; // N이 0일 때, 0 ~ 100 까지 101개의 수
        primeNumbers[0] = false; // 1
        primeNumbers[1] = false; // 2

먼저 0 ~ 100까지의 101개의 배열을 생성해주고 0, 1은 제외 시킨다.

 // 모두 true로 초기화
 for (int i = 2; i <= number; i++) {
 	primeNumbers[i] = true;
 }

2부터 모두 소수라 가정하고 true로 지정한다. 

for (int i = 2; i <= Math.sqrt(number); i++) {
	if (primeNumbers[i] == false)
    	continue;
    for (int j = i + i; j <= number; j += i) {
    	primeNumbers[j] = false;
    }
}

에라토스테네스의 체 공식으로

1. 이미 제외시킨 숫자라면 다음 숫자

2. 제외시킨 숫자가 아니라면 그 수를 제외하고 배수를 false로 변환한다.

다음과 같은 결과를 얻을 수 있다.

전체 코드

import java.util.Scanner;

public class eratos {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("2이상의 숫자를 입력해 주세요 : ");
        int N = scanner.nextInt();

        fintPrimeNumber(N);
    }

        private static void fintPrimeNumber(int number) {
        Boolean[] primeNumbers = new Boolean[number + 1]; // N이 0일 때, 0 ~ 100 까지 101개의 수
        primeNumbers[0] = false; // 1
        primeNumbers[1] = false; // 2

        // 모두 true로 초기화
        for (int i = 2; i <= number; i++) {
            primeNumbers[i] = true;
        }

        for (int i = 2; i <= Math.sqrt(number); i++) {
            if (primeNumbers[i] == false)
                continue;
            for (int j = i + i; j <= number; j += i) {
                primeNumbers[j] = false;
            }
        }

        System.out.println();
        System.out.println(number + "이하의 소수 입니다.");
        
        for (int i = 0; i < primeNumbers.length; i++) {
            if (primeNumbers[i]) {
                System.out.print(i + " ");
            }
        }
    }
}