[백준/9020] 골드바흐의 추측 (with 파이썬)

✔ 문제

---

✔ 풀이

🤢 풀다가 포기한 코드

t = int(input())

nums = []

for i in range(2, 10000):
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            break
    else:
        nums.append(i)

for _ in range(t):
    n = int(input())
    sums = []
    mins = []

    for i in nums:
        for j in nums:
            if i + j == n:
                sums.append([i, j])
                break

# 미완

코드가 점점 더 길어지고... 위에서 더 필요한 코드는

1. 예를 들어 n이 8일 때 [3, 5] [5, 3]이 저장되는데 이를 [3, 5] 하나만 저장되게 하는 코드

2. 만약 1번을 수정하지 않았을 때 sums에 저장된 i, j의 가장 작은 차이를 구하기 위해 mins 함수에 i - j 값을 저장하는 코드

3. 2번 수행했을 경우 가장 작은 차이의 값의 인덱스를 구해 출력하게 해야하지만 min()을 사용할 경우 음수가 답으로 출력될 수 있기 때문에 이를 방지하는 코드

등등... 이 필요하다... 풀다보니까 이게 아닌 것 같아서 노선 변경.. 🥺

 

 

🙇‍♀️ 답안 코드

def is_Prime(n):
    if n == 1:
        return False

    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

t = int(input())

for _ in range(t):
    n = int(input())

    a, b = n // 2, n // 2

    while a > 0:
        if is_Prime(a) and is_Prime(b):
            print(a, b)
            break
        else:
            a -= 1
            b += 1

---

✔ 설명

1. 소수를 미리 구해놓는 것이 아니라 해당 숫자가 소수인지 판별하는 함수를 미리 구현한다. (def is_Prime)

2. n을 입력 받아서 n // 2 값을 a, b로 나눠 저장한다.

    ㄴ 가장 작은 차의 소수를 구할거면 n // 2를 한 값으로 구하는 것이 다른 판별 코드 없이 제일 빠르다.

3. a는 -1씩, b는 +1 씩 해 a, b 둘 다 소수인 값을 구하면 된다.

    ㄴ n을 2로 나눈 후 a, b를 동시에 -1, +1 하므로 a+b의 값은 계속 n이 나온다.

 

---

✔ 후기

처음에 짜던 코드로 계속 했으면 분명히 시간 초과가 났을 것이다...

계속 풀다가 for문의 연속이길래 이게 아닌 것 같아서 멈췄다..

그리고 다른 방법이 도저히 생각이 안나서 구글링 해봤더니 다른 방법들이 많이 있었다..

n // 2를 하면 따로 if a + b == n: 이라는 조건을 쓰지 않아도 된다는 점이 정말... 머리의 전구가 딱! 켜지는 순간이었다.😥