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

6588번: 골드바흐의 추측 (acmicpc.net)

6588번: 골드바흐의 추측

 

내가 처음에 생각한 방법은,

2부터 입력받은 num값 범위 까지 소수인 애들을 리스트로 뽑은 후에,

리스트에 for 문 돌려서 -> if num-list[i] in list

num-list[i] 가 list안에 존재하면, print(num = (num-list[i]) + (num-(num-list[i])) 이렇게 나오게 작성했다.

 

 

함수로 작성해서 값이 하나만 나오게까지 고쳤는데, 내가 원하는건 3+17인데 7+13이 나와버리는 것이다.

(아직도 저건 어떻게 고쳐야하는지 모르겠음)

 

인터넷을 찾아보니 '에라토스테네스의 체' 라는 것을 활용해서 푼다는데,

도대체 먼말인지 모르겠음

그래서 내가 짜논 코드를 어떻게든 살릴 수 없나 고민하다가

같이 코테 스터디하는 친구가 비스므레한 방법으로 풀었길래 나도 활용해보았다!

 

나의 첫 코드는 무식하게 함수 하나를 풀로 돌렸는데,

소수를 구하는 함수와 출력문을 따로 분리했다.

 

import sys

def sosu(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:
    num = int(sys.stdin.readline())
    for i in range(3,num+1):
        if sosu(i):
            if sosu(num-i):
                print("{} = {} + {}".format(num,i,num-i))
                break
                
    if num == 0:
        break

 

문제에 a와 b는 3부터 시작하는 홀수라고 정해져있기 때문에 i의 범위를 3부터 시작해야함
이렇게 하고 보니 생각보다 간단한 문제였다.

소수를 구할 땐 루트 값 까지만 돌려도 된다는 것을 잊지말것 !

 

원래 num(int(input())을 자주 애용했는데, 이번에 얘 때매 시간초과에 걸렸다.

앞으로 input 대신 sys.stdin.readline을 쓰려고 노력해봐야겠다.