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

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

6588번: 골드바흐의 추측

 

문제 파악

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

 

 

문제 해결 프로세스

생각보다 쉬웠던 문제이다.

이전에 에라토스테네스의 체에 대한 문제를 풀어서 그런지 문제 해결방법은 한 3분? 정도 고민한 것 같다.

 

먼저 두 홀수 소수에 대한 정보를 table에 나타내야 된다고 생각했다. 그 방법으로는 에라토스테네스의 체를 생각했다.

여러 값들을 연산하기 위해서는 미리 table로 정보를 만들어줘야한다고 생각한다.

 

+ 알고리즘 분류에서 에라토스테네스의 체도 분류도 있으니, 힌트를 얻으려면 보면 좋을 듯!

 

 

가장 기본적으로, 소수를 구하는 방법으로는, 해당 주어진 숫자를 2부터 본인숫자까지 나누어지지 않은다면 소수인데, 아니면 소수가 아닌 것이다. 그렇게 해당 주어진 숫자를 차례차례 계산하는 방법도 있기는 한데, 시간 복잡도가 높을 것이다.

2에서부터 자기 자신까지 모두 나눴을 때 나머지가 0이 되면 소수가 아니며, 0이 한번도 나오지 않는다면 소수이다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

구하려는 숫자가 커질 수록 시간이 그만큼 늘어나게 되므로 비효율적이다. 소수를 찾는데 가장 효율적인 알고리즘은 에라토스테네스의 체 이다.

 

 

 

에러 봉착

처음에 계속 런타임에러, 타입에러가 떠서 무엇이 문제이지?

 

이번에도 같은 실수를 반복했다...

for i in range(2, num/2+1):

이렇게 하면, 타입에러뜨고

for i in range(2, num//2+1):

이렇게 해주어야 한다!

 

내 인터프리터에서는 잡지 못하는데, 온라인 컴파일러는 바로 잡아주네요,, 호호

덕분에 빠르게 해결 완료

 

해결 코드

아주 EZEZ

나는 end= ' ' 이게 안돼서 계속 시간을 많이 썼는데, 아직도 해결을 못했다..

그래서 온라인 컴파일러 활용해서 했다.. 흑

import sys
input = sys.stdin.readline

table = [1 for i in range(1000001)]
table[1] = 0

for i in range(2, 500001):
    if table[i] ==1:
        j = 2
        while i*j <= 1000000:
            table[i*j] = 0
            j += 1

while(True):
    num = int(input())
    if(num == 0):
        break
    flag = 0
    for i in range(2, num//2+1):
        if(table[i]==1):
            if(table[num-i] == 1):
                flag = 1
                print(num, end=' = ')
                print(i, end=' + ')
                print(num-i)
                #print(num, "=", i, "+", num-i)
                break
    if(flag == 0):
        print("Goldbach's conjecture is wrong.")