BOJ 9020 : 골드바흐의 추측[pypy3]

문제

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

풀이

이번 풀이는 pypy3으로 진행되었는데, 그 이유는... python3으로는 시간초과가 계속 발생했기 때문이다. 내 코드로는 도저히 시간이 단축이 안된다... ㅠ

아래는 내가 시도했었던 코드 [python3 : 시간초과] [pypy3 : 통과]

import sys

def goldvagh(n):
    prime_factor = eratosthenes(2,n)
    goldvagh_number = []
    for i in prime_factor[:int(len(prime_factor)/2)+1]:
        if n - i in prime_factor and n >= i:
            goldvagh_number.append([i,n-i])
    
    min = 10000000
    min_gold = 0
    if len(goldvagh_number) >= 1:
        for i,d in enumerate(goldvagh_number):
            if min > (d[1] - d[0]) >= 0:
                min = d[1] - d[0]
                min_gold = goldvagh_number[i]
        return min_gold
    else:
        return False

def eratosthenes(n, m):
    check = [0] * (m + 1)
    result = []
    for i in range(2, m + 1):
        if check[i] == 0:
            for j in range(i*2, m + 1, i):
                if check[j] == 0:
                    check[j] = 1

    for i in range(n, m+1):
        if check[i] == 0:
            result.append(i)
    if 1 in result:
        result.remove(1)
    return result


if __name__ == '__main__':
    T = int(sys.stdin.readline())
    # era = eratosthenes(2,10000)
    for _ in range(T):
        data = goldvagh(int(sys.stdin.readline()))
        if data:
            print(data[0], data[1])

다른 분의 코드 아이디어를 참조했다. https://week-year.tistory.com/171

[python] boj 17103 골드바흐 파티션

1. 참고 할 중요 내용은 "단순 반복되는 코드는 꼭 밖에 빼자" python3의 속도를 그나마 높여준다.
2. 속도를 항상 최소화 할 수 있는(단순히 코드를 통과하는 게 아닌 것을 목표로) 코드 구조를 구성하자.

import sys

def bj9020_ver2():
    prime = [1 for i in range(10001)]
    prime[0], prime[1] = 0, 0

    num = 2
    while num <= int(10001 ** (0.5)):
        if prime[num]:
            for i in range(num + num, 10001, num):
                prime[i] = 0
        num += 1

    T = int(sys.stdin.readline())
    for test in range(T):
        n = int(sys.stdin.readline())
        for i in range(n//2,1,-1):
            if prime[i] and prime[n-i]:
                print(i,n-i)
                break

bj9020_ver2()

 

나는 에라토스테네스의 체를 주어진 범위의 최대 (10000)까지 세팅해서 두기도 했었고, 이것을 함수 내부에서 계속 반복한 것 때문에 속도가 조금 느렸던 것 같다.(작은 수는 통과되기도 함 : 최대 9%까지....) T에 따라서 받는 수들의 최대값을 에라토스테네스의 체 세팅을 하고 그 값을 비교할 때도 갯수의 반 까지 만(i = n-i 이기 때문) 계산하는 것.. 기본적인 코딩 규칙으로 생각하자.