백준 알고리즘 6588번: 골드바흐의 추측

문제 정보

---

 

6588번: 골드바흐의 추측

 

 

핵심

---

에라토스테네스의 체 활용하여 소수 구하기

두 소수의 합으로 target number를 만들어내는 알고리즘 생각하기

 

 

풀이

---

from sys import stdin

case = list(map(int, stdin.readlines()[:-1]))
maxnum = max(case)

# 에라토스테네스의 체 활용 소수 구하기
prime = [True for _ in range(maxnum + 1)]
prime[0], prime[1] = False, False

for i in range(2, int(maxnum**0.5)+1):
    if prime[i]:
        j = 2
        while i*j <= maxnum:
            prime[i*j] = False
            j += 1

primes = [i for i in range(len(prime)) if prime[i]]

def solve(target):
    for s in range(1, target//2):
        if prime[target-primes[s]]:
            print(f'{target} = {primes[s]} + {target-primes[s]}')
            return
    print('Goldbach\'s conjecture is wrong.')



for c in case:
    solve(c)

 

먼저, 나는 에라토스테네스의 체를 활용하여 입력받은 수들 중 가장 큰 수의 크기로 prime 배열을 만들어 주었다

그 후 n을 만들 수 있는 a와 b를 구하면 되는데, 해당 방법은 다음과 같다

 

def solve(target):
    for s in range(1, target//2):
        if prime[target-primes[s]]:
            print(f'{target} = {primes[s]} + {target-primes[s]}')
            return
    print('Goldbach\'s conjecture is wrong.')

사실 간단한데,

start를 1부터(숫자 3) 전체 크기의 반까지의 범위로 두고

만약 짝을 이루는 수가 소수라면, 이를 출력해주면 된다

이 경우 처음 나오는 경우가 b-a가 가장 큰 것이기 때문에, 이를 판단하지는 않아도 되어 간단하다

 

예를 들어, 20이라는 수를 입력받았다면

3으로 시작하여 20(target) - 3(s) = 17(짝을 이루는 수) 가 소수라면 이 경우가 답이 되는 것이다

 

42의 경우에도

i)  42(target) - 3(s) = 39(짝을 이루는 수) -> 이 경우 39는 소수가 아니므로 s를 1 올림

ii) 42 - 5(s) = 37 -> 이 경우 37은 소수이므로 이를 출력함 (답)

 

이러한 알고리즘을 활용하여 이 문제를 풀이할 수 있다

 

 

고찰

---

처음에 투 포인터를 활용하여 문제를 풀어보고자 했지만, 효율이 안나왔던 것 같다

다른 풀이도 생각해봤지만 안풀려서 살짝 다른 풀이를 참고 후 풀이 방안을 생각해 낸 것이다

더욱 빠르게 풀 수 있도록 열심히 노력할 것이다

 

 

참고

---

GitHub - dduneon/CodingTestPy

 

에라토스테네스의 체?

백준 알고리즘: 1978번 소수 찾기