[백준] 6588번 골드바흐의 추측

💡문제접근

• 에라토스테네스의 체를 이용하여 쉽게 해결가능한 문제

📌시간초과1

import sys
input = sys.stdin.readline

arr = [True] * 1000001
arr[0] = False
arr[1] = False
for i in range(2, 1000001):
    if arr[i]:
        for j in range(i*i, 1000001, i):
            arr[j] = False

while True:
    n = int(input().strip())
    if n == 0:
        break

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

📌시간초과2

import sys
input = sys.stdin.readline

while True:
    n = int(input().strip())
    if n == 0:
        break
    arr = [True] * (n+1)
    arr[0] = False
    arr[1] = False
    for i in range(2, n+1):
        if arr[i]:
            for j in range(i*i, n+1, i):
                arr[j] = False

    a = 0 
    b = n
    while True:
        if a > b:
            print("Goldbach's conjecture is wrong.")
            break
        if arr[a] and arr[b]:
            print(str(n), "=", str(a), "+", str(b))
            break
        a += 1
        b -= 1

📌시간초과3

import sys
input = sys.stdin.readline

arr = [True] * 1000001
arr[0] = False
arr[1] = False
for i in range(2, 1000001):
    if arr[i]:
        for j in range(i*i, 1000001, i):
            arr[j] = False

while True:
    n = int(input().strip())
    if n == 0:
        break

    a = 0
    b = n
    while True:
        if a > b:
            print("Goldbach's conjecture is wrong.")
            break
        if arr[a] and arr[b]:
            print(str(n), "=", str(a), "+", str(b))
            break
        a += 1
        b -= 1

💡코드(메모리 : 39068KB, 시간 : 2072ms)

import sys
input = sys.stdin.readline

arr = [True] * 1000001
arr[0] = False
arr[1] = False
for i in range(2, 1001):
    if arr[i]:
        for j in range(i*i, 1000001, i):
            arr[j] = False

def check(n):
    for i in range(2, n):
        if arr[i] and arr[n-i]:
            print(str(n), "=", str(i), "+", str(n-i))
            return 0
    return 1

while True:
    try:
        n = int(input().strip())
        if n == 0:
            break
        if check(n):
            print("Goldbach's conjecture is wrong.")
    except EOFError:
        break

💡소요시간 : 30m