[ 백준 - 9020 ] 골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

마지막으로 문제를 풀었던 4달전과 코드가 얼마나 달라졌는지 확인할겸 풀었던 문제들을 다시 풀고 있다.

잊었던 감각도 찾고, 코딩 테스트도 준비 할겸

 

문제 풀이 방법은 역시 여러번 풀어서 그런건가 머릿속에 있어서 어렵지는 않게 풀었다.

파이썬과 자바의 풀이 로직은 같지만 자바 까먹을까봐 같이 푼다.

---

[ 📌 풀이 ]

먼저 소수를 구하는 방법으로는 제곱근을 사용하는 방법이 있지만 나는 범위가 주어졌고, 문제에서 여러가지 숫자가 케이스로 주어지기 때문에 먼저 소수를 에라토스 테네스의 체로 구하고 테스트 케이스를 실행했다.

 

• 에라토스테네스의 체를 이용하여 범위내에서 소수들만 표시 해놓기
• 골드바흐의 추측에 만족하는 소수 2개 찾기
  • 문제의 예시를 읽고, 문제를 풀 다 보면 모든 소수를 하나씩 대입해서 푸는건 오래 걸리기 때문에 수를 이항해서 푸는게 더 효과적이라고 생각이 되어서 밑에 식과 같이 풀게 되었다. (문제를 계속해서 풀다 보니까 개선점이 하나씩 나왔다.) 
    • A = B + C
    • A - B = C
• 골드바흐 추측 부분에서 같은 수를 반복하기 때문에 나누기 2를 해줬다.
  • ex) 10의 경우 (7, 3) (3, 7) 같은 수로 두 쌍이 나오기 때문이다.

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체 - 나무위키

---

[ 📌 코드 - Python (정글 과정 중 풀이) ]

import sys
import math

T = int(sys.stdin.readline())
prime_list = [False for _ in range(10001)]

for idx in range(2, len(prime_list)):
    if prime_list[idx]:
        continue

    next_prime = idx + idx
    if idx > 1000:
        break

    while next_prime < 10001:
        prime_list[next_prime] = True
        next_prime += idx

for _ in range(T):
    num = int(sys.stdin.readline())

    List = list(range(2, num + 1))
    bound = int(num / 2)

    for item in range(bound, 0, -1):
        if prime_list[item]:
            continue

        gap = num - item

        if not prime_list[gap]:
            print(min(gap, item), max(gap, item))
            break

 

[ 📌 코드 - Python ]

"""
# Author    : Lee In Bok 
# Date      : 2023.12.24(Sun)
# Spend Time: 35m 50s
# Runtime   : 31120 KB
# Memory    : 72 ms
# Algoritm  : Prime Number
"""

import sys
input = sys.stdin.readline

MAX = 10001
arr = [True for _ in range(MAX)]

for num in range(2, MAX):
    if not arr[num]:
      continue

    next = num + num
    while next < MAX:
      arr[next] = False
      next = next + num

T = int(input())

for _ in range(T):
  num = int(input())

  for idx in range(num // 2, 0, -1):
    if not arr[idx]:
      continue

    gap = num - idx

    if arr[gap]:
      print(idx, gap)
      break

[ 📌 코드 - Java ]

/**
* Author    : Lee In Bok 
* Date      : 2023.12.24(Sun)
* Spend Time: 35m 50s
* Runtime   : 17004 KB
* Memory    : 208 ms
* Algoritm  : Prime Number
 */

package BaekJoon.DivisorMultiplePrimeNumber.Q9020;

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

public class Q9020_GoldBach {

  public static final int MAX = 10001;
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int T = Integer.parseInt(br.readLine());
    boolean[] arr = getPrimeNumbers();

    for(int i = 0; i < T; i++){
      int num = Integer.parseInt(br.readLine());

      for(int j = num/2; j <= num; j++){
        if(arr[j]){
          continue;
        }

        int gap = num - j;

        if(!arr[gap]){
          sb.append(gap + " " + j + "\n");
          break;
        }
      }
    }
    System.out.println(sb.toString());
  }

  public static boolean[] getPrimeNumbers(){
    boolean[] arr = new boolean[MAX];

    for(int num = 2; num < MAX; num++){
      if(arr[num]){
        continue;
      }

      int next = num + num;
      while(next < MAX){
        arr[next] = true;
        next += num;
      }
    }

    return arr;
  }
}

---

[ 📌 결과 - Python & Java ]

[ Result - Python & Java ]