백준 6588 [골드바흐의 추측] 파이썬

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

6588번: 골드바흐의 추측

# 백준 6588 골드바흐의 추측
import sys
input = sys.stdin.readline


def isPrime(num):
    i = 3
    while i**2 <= num:
        if num % i == 0:
            return 0
        i += 1
    return 1


while True:
    check = 0
    n = int(input().rstrip())
    if n == 0:
        break
    for i in range(3, n+1, 2):
        n1 = i
        n2 = n-i
        if n1 > n2:
            break
        else:
            check = isPrime(n1)+isPrime(n2)
            if check == 2:
                break
    if check != 2:
        print("Goldbach's conjecture is wrong.")
    else:
        print("{} = {} + {}".format(n, n1, n2))

소수 판별을 통해 계산하였다. python3 로는 시간초과가 발생하여, pypy3 로 제출하였다. 

시간초과가 발생하지 않게 해결한 풀이가 있어서 첨부한다.

import sys
import math

input = sys.stdin.readline

arr=[True]*1000001

for i in range(2,int(math.sqrt(1000001))+1):
    if arr[i]:
        for j in range(i+i,1000001,i):
            arr[j]=False

while True:
    n=int(input())
    flag=0
    if n==0:
        break
    
    for i in range(3,n//2+1):
        if arr[i]==True and arr[n-i]==True:
            print('%d = %d + %d'%(n,i,n-i))
            flag=1
            break

    if flag==0:
        print("Goldbach's conjecture is wrong.")

https://mincheolsong.github.io/boj/boj6588/

[백준 6588번-파이썬]골드바흐의 추측

나누기 연산을 하지 않고, 배열에 false를 변경하는 방식으로 빠르게 계산할 수 있었다.