[CodingStudy] Beakjoon 6588번 골드 바흐의 추측

틀린 부분이 있다면 언제든지 댓글 남겨주세요! 

 

---

Beakjoon 6588번_골드 바흐의 추측

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

6588번: 골드바흐의 추측

효율성을 따지는 부분이 어려운 문제이다.

우선 핵심은 소수 판별시 에라토스테네스의 체 이용!

에라토스테네스의 체는 여러개의 소수 판별에 용이하다.

알고리즘에 대해 간단히 설명해보면 다음과 같다.

 

1. 모든 수에서 가장 작은 소수 2 > 나머지 수 중 2의 배수 모두 지움
2. 다음 작은 소수 3 > 나머지 수 중 3의 배수 모두 지움
3. 반복

---

처음에 짰던 코드이다. 

아래와 같이 입력받을 때마다 소수를 찾으면 시간초과가 난다.

def prime(ni):
    alllist=[False, False]+[True]*(ni-1) # 0,1 제외
    primelist=[]
    
    for k in range(2, ni):
        if alllist[k]:
            primelist.append(k)
            j=2
            while k*j<=ni:   # 소수의 배수 지움 
                alllist[k*j]=False
                j+=1

    return primelist

nlist=[]
maxx=1

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

for ni in nlist:
    pri=prime(ni)
    
    for n in pri:
        prisub=ni-n
        if prisub in pri:
            maxx=max(prisub, maxx)
            
    print(ni, ' = ', ni-maxx,' + ', maxx)

---

처음 코드에서 효율성을 높이기 위해 바꾼 방식은 3가지가 있다.

 

1. 입력값을 input이 아닌 sys 라이브러리의 sys.stdin.readline함수로 사용

2. 에라토스테네스의 체 이용시 입력값마다 소수를 찾는 것이 아니라 미리 구해두고 사용

   이때 따로 소수 리스트를 만들면 그 또한 시간이 소요되기 때문에 만들지 않음!

3. 소수의 배수를 지울 때 while문이 아닌 for문 사용

   변수도 하나 줄어들게 됨!

 

import sys

alllist=[False, False]+[True]*1000000 # 0,1 제외
    
for k in range(2, 1000001):
    if alllist[k]:
        for i in range(k+k, 1000001, k):   # 소수의 배수 지움
            alllist[i]=False

while True:
    ni=int(sys.stdin.readline())    # input보다 시간 단축
    if ni==0:
        break
    
    i=0
    for i in range(2, 1000001):
        if alllist[ni-i] and alllist[i] and (ni-1)>0:
            print(ni, '=', i,'+', ni-i)    
            break
        i+=1
    else:       # for-else문 > for문이 다 돌면 들어옴
        print("Goldbach's conjecture is wrong.")

그리고 출력문에 띄어쓰기 조심! 따로 넣지 않아도 변수 간 띄어쓰기가 하나씩 들어간다.