[수학] [BJ6588] 골드바흐의 추측

코드 플러스

🚩 문제 설명

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

6588번: 골드바흐의 추측

 

⏱️ 시간 복잡도
▪ 2부터 N 까지의 수 중에서 소수를 골라 합으로 나타낸다.
▪ 시간복잡도는 O(abs(N) x logN) 으로 해결할 수 있다.

◾ 두 소수의 합으로 해당 테스트 케이스의 수를 나타내는 문제

◾ 골드바흐의 추측

• 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
• ex) 3 + 5 = 8

 

 

---

 

 

 

✅ 입출력

1) 각각의 테스트 케이스가 주어진다.
return ➡️ 각각의 테스트 케이스의 정수를 소수의 합으로 출력한다.

✔️ 예제 1

8
20
42
0

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

 

 

 

---

 

 

 

📑 문제 풀이 (1)

with 파이썬 (Python)

import sys

nums = []
while True:
    num = int(sys.stdin.readline().strip('\n'))

    if num == 0:
        break

    nums.append(int(num))


def isPrime(n):
    prime = [0] * (n + 1)
    memo = [0] * (n + 1)
    pn = 0

    for i in range(2, n + 1):
        if memo[i] == 0:
            pn += 1
            prime[pn] = i

            for j in range(abs(i), n + 1, i):
                memo[j] = 1

    prime = prime[1:pn + 1]
    return prime


for n in nums:
    prime = isPrime(n)

    for p in prime:
        if p % 2 != 0:
            leaf = n - p
            if leaf % 2 != 0 and leaf in prime:
                print(f'{n} = {p} + {leaf}')
                break

◾ 이러면 시간초과가 걸린다.. 당연함.. 반복문이 4개나 들어감..

 

📑 문제 풀이 (2)

import sys

MAX = 1000000
prime = [0] * (MAX + 1)
memo = [0] * (MAX + 1)
pn = 0

for i in range(2, MAX + 1):
    if memo[i] == 0:
        pn += 1
        prime[pn] = i

        for j in range(i * i, MAX + 1, i):
            memo[j] = 1

while True:
    num = int(sys.stdin.readline().strip('\n'))

    if num == 0:
        break

    for i in range(pn):
        if memo[num - prime[i]] == 0:
            print(f'{num} = {prime[i]} + {num - prime[i]}')
            break

💬 Point

➡️  100만 까지의 소수를 모두 구해놓는다.
➡️  memo[num - prime[i]]

◾ 100만 까지의 소수를 구하는 시간복잡도는 10^3 x 6 과 같다.

◾ 따라서 우선적으로 100만까지의 소수를 모두 구해놓는다.

◾ 문제의 이해는 다음과 같다.

◾ 만약 8 = a + b 라고 한다면

• a와 b 둘다 소수이기 떄문에
• memo[a] = 0
• memo[b] = 0 이다.
• 8 - a = b 이다.

◾ 따라서 memo[8 - a] = memo[b] 이고 이를 식으로 풀면

◾ memo[num - prime[i]] 라고 할 수 있다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 코드 플러스 골드바흐의 추측 파이썬 python

# 백준 6588 골드바흐의추측 파이썬 python

---