[Python] 백준 6588 골드바흐의 추측 | 시간 초과 | 에라토스테네스의 체 | 소수 구하기 끝판왕

~실버1~

 

아무리 고쳐도 41%에서 시간 초과,,,,

광기의 끝을 보여주기로 했다

 

하늘에서 "너는 '에라토스테네스 체' 완전히 이해할 때까지 굴려야지 안 되겠다"

라고 한 것 같은 느낌이었다,,,

 

 

말도 안 되는 상황인게

함수 안에 코드를 넣고 호출하는 방식으로 하니까

시간 초과가 안 뜬다는 사실을 깨달았기 때문이다,,,

 

---

 

 

에라토스테네스의 체

소수를 구하기 위한 방법론이다.

2부터 시작(1은 소수가 아님) 하여 N까지 True값을 가진 배열을 만들고, 소수가 아닌 값은 제외(False)하여 나가는 방식이다

주의할 점은 2부터 N까지 모두 확인하는 것이 아닌 N**0.5, 즉 N의 제곱근까지 까지만 확인하면 된다.

 

 

왜 제곱근까지만 구하면 될까?

예를 들어 N의 값으로 12가 주어졌다고 생각해보자

12를 곱셈으로 표현할 수 있는 수는 1, 2, 3, 4, 6, 12이다.

1 * 12     2 * 6      3 * 4      4 * 3      6 * 2      12 * 1

 

12의 제곱근 3.464 까지이고 이를 기준으로 대칭을 이루며 다시한번씩 등장하고 있음을 알 수 있다.

그러므로 제곱근 이전까지 소수임이거나 소수가 아님이 판별된 수들은 반복되어 다시 등장하므로 볼 것도 없다는 뜻이다.

 

이를 생각하면서 제외할 값들을 보면

 

2는 소수이다. 그러나 2의 배수들은 소수가 아니므로 전부 제외한다.

3은 소수이다. 그라니 3이 배수들은 소수가 아니므로 전부 제외한다.

......(반복)

이미지 출처 : 위키백과

해당 방법을 통해서 빠르게 소수인 값을 담은 배열을 생성할 수 있다.

해당 배열을 사용하여 홀수인 소수의 합을 구할 수 있을 것이다!

 

 

<최종 코드>

import sys

input = sys.stdin.readline


def solution():
    # 에라토스테네스의 체
    goldbach = [True for _ in range(1000001)]
    for i in range(2, 1001):  # 100000의 제곱근
        if goldbach[i]:
            for j in range(i*i, 1000001, i):
                goldbach[j] = False

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

        for i in range(3, n):
            if goldbach[i] and goldbach[n - i]:
                print("%d = %d + %d" % (n, i, n - i))
                break
        else:
            print("Goldbach's conjecture is wrong.")


solution()

solution 함수안에 해당 코드를 작성하지 않으면 시간 초과가 발생할 것이다,,

왜 그런지는 정확한 이유를 모르겠습니다ㅠ 혹시 이유를 아시는 분이 계시다면 알려주시면 감사하겠습니다*^^*