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

문제 핵심

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

풀이 과정

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

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

 

소수 찾기 ( 에라토스테네스의 체 ) - JAVA

에라토스테네스의 체 는 소수를 찾는 쉽고 빠르게 찾을 수 있는 방법이다.( 고대 그리수 수학자 에라토스테네스가 발견 ) 알고리즘다음과 같은 알고리즘을 따른다.0 ~ 50 까지의 수를 찾고자 할

p-coding.tistory.com

 

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 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

 

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

  2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

 

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

  2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

 

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 + " ");
            }
        }
    }
}
반응형

'알고리즘' 카테고리의 다른 글

플라비우스 요세푸스 순열  (2) 2025.02.28
[ 자료구조 ] 큐 ( Queue ) - JAVA  (0) 2025.02.26
스택 ( 자료구조 ) - JAVA  (0) 2025.02.04
[ 알고리즘 ] 선택 정렬  (2) 2024.12.12

+ Recent posts