[BOJ] 6588: 골드바흐의 추측

이슬비·2022년 6월 7일

boj 수학 자료구조&알고리즘

Algorithm

목록 보기

38/110

3번이나 풀었는데 3번 다 시간초과 or 런테임에러가 났다 ㅋㅋㅋㅋㅋ 뭔가 풀 수 있을 것 같아서 계속 도전했는데 장렬히 실패.

6588: 골드바흐의 추측

1. 내 풀이 1: 실패

import sys
def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    decimal = []
    for i in range(3, round(n/2)+1):
        if isPrime(i):
            decimal.append(i)
    temp = 0
    while True:
        a = decimal[temp]
        if isPrime(n-a):
            b = n-a
            print(f'{n} = {a} + {b}')
            break
        else:
            temp += 1
            a = decimal[temp]

맞은 풀이가 아니니까 간단하게 설명하고 넘어가자면, 일단 들어온 변수의 절반 만큼 3부터의 소수를 구해준다. (isPrime 함수 이용) 그 후에 구해진 소수를 빼가면서 (원래 수) = (제일 작은 소수) + (뺀 소수)의 형태로 구한다.

결과는,

2. 내 풀이 2: 실패

import sys
def isPrime(num):
    if num == 1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num%i == 0:
                return False
        return True

while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    decimal = [3,5,7,11,13,17,19,23,29,31]
    temp = 0
    while True:
        a = decimal[temp]
        if isPrime(n-a):
            print(f'{n} = {a} + {n-a}')
            break
        else:
            temp += 1

과연 이것만큼 바보같은 풀이가 있을까...? n의 최대가 1,000,000이길래 넣어보니 결과가 1000000 = 17 + ~로 나왔다.
앞 쪽에서 시간초과 난 게 isPrime + append + temp 더하기라고 생각이 되었다. 그래서 ㅋㅋㅋ 3부터 17까지만 decimal이라고 하고 list를 선언했다.
결과는,

수많은 런타임 에러 ~... 그 이유는 temp에서 계속 1을 더해주는데 내가 정한 건 17까지 밖에 없으니까... 그래서 처음에는 계속 소수를 list에 추가하다가 이건 아니다 싶어서 다른 방법을 생각해보았다.

3. 내 풀이 3: 실패

import sys
while True:
    n = int(sys.stdin.readline())
    if n == 0:
        break
    TF = [False, False] + [True]*(n-1)
    decimal = []
    for i in range(2, n+1):
        if TF[i]:
            decimal.append(i)
            for j in range(2*i, n+1, i):
                TF[j] = False
    temp = 0
    while True:
        a = decimal[temp]
        if isPrime(n-a):
            print(f'{n} = {a} + {n-a}')
            break
        else:
            temp += 1

아레토스테네스의 체를 이용해서 소수를 구해보자라고 생각했다. 당연히 ~ 시간초과가 났다.
일단 1,000,000 찍는데 1초라도 버벅거린다? 그러면 일단 실패했다고 봐야지... 그래서 화가 나부러서~ 답을 봤다.

4. 다른 풀이

아래의 블로그를 참고했다.
https://velog.io/@dding_ji/%EB%B0%B1%EC%A4%80-6588.-%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%EC%9D%98-%EC%B6%94%EC%B8%A1-Python-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4

from sys import stdin

array = [True for i in range(1000001)]

for i in range(2, 1001):
    if array[i]:
        for k in range(i + i, 1000001, i):
            array[k] = False

while True:
    n = int(stdin.readline())

    if n == 0: break

    for i in range(3, len(array)):
        if array[i] and array[n-i]:
            print(n, "=", i, "+", n-i)
            break