6588

날짜 : 2022. 12. 13 // 수정 : 2023.02.12

사용 언어 : python

 

문제

 

 

코드

시간초과 발생(재채점 이후)

import sys


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


while True:
    n = int(sys.stdin.readline())
    if n < 6 or n > 1000000 or n % 2 == 1: break
    a = 3
    b = n - a
    while True:
        if a > b: print("Goldbach's conjecture is wrong.")
        if isprime(a) and isprime(b):
            print("%d = %d + %d"%(n, a, b))
            break
        a += 2
        b -= 2

 

TLE 해결 코드

import sys

isprime = [True] * 1000001
isprime[0] = False
isprime[1] = False

for i in range(2, len(isprime) // 2):
    for j in range(i, len(isprime), i):
        if j == i: continue
        else: isprime[j] = False  # 배수 필터링


while True:
    n = int(sys.stdin.readline()) # 임의의 짝수
    if n < 6 or n > 1000000 or n % 2 == 1: break  # 조건 부합 x
    a = 3  # 초기값
    b = n - a  # 차이 가장 크게
    while True:
        if a > b: print("Goldbach's conjecture is wrong.")
        if isprime[a] and isprime[b]:  # 둘 다 소수
            print("%d = %d + %d"%(n, a, b))
            break
        a += 2
        b -= 2

 

 

 

풀이

- 따로 소수 리스트를 만들지 않고 a와 b의 소수 여부를 그때그때 구하는 방식으로 문제를 해결했다.

- 소수 여부는 에라토스테네스의 체를 구현해서 소수라면 True, 아니라면 False를 리턴한다.

- a = 3, b = n - 3 으로 시작하여 둘 중 소수가 아닌 경우 a는 2를 가산, b는 2를 감산하는 방식으로 반복문을 진행한다.

(차이는 a가 최소일 때, b가 최대일 때이므로 반복문이 진행되면서 차이를 굳이 찾을 필요는 없다.)

 

 

알게된 점

- n의 범위에 따른 탈출문을 만들지 않아서 계속 틀렸다.

- 다른 문제에서는 크게 문제 없었는데 왜 이 문제만 그러는지.. 이거 하나로 꽤 많은 시간을 허비했다 ㅇㅅㅇ

 

* 추가

- 재채점 이후 시간초과가 발생해서 일일이 소수를 구하기보다는 1~100만까지의 소수 여부를 저장한 리스트를 생성 후 입력할 때마다 체크하는 방식으로 문제를 해결했다.

 

참고 사이트

-