[BOJ] 골드바흐의 추측 - python

SUN·2022년 7월 13일
0

algorithm

목록 보기
4/30

오늘 풀 문제는 골드바흐의 추측이다.


풀이 과정

우선 이 문제를 보고 제일 먼저 든 생각은 그냥 1부터 n까지 중에서 소수를 찾아서 리스트로 만들고 그 중에서 조합을 짜서 합이 n이 되는 걸 찾은 다음에 그 두 수의 차이가 제일 적은 걸 출력하면 되지않나? 해서 그렇게 짜보았다


from itertools import combinations

t = int(input())


def get_primes(n):
    primes = []

    for i in range(2, n):
        primes.append(i)

        for j in range(2, i):
            if i % j == 0:
                primes.pop()
                break

    return primes


for i in range(t):
    n = int(input())

    primes = get_primes(n)
    # print(primes)

    prime_combs = list(combinations_with_replacement(primes, 2))
    # print(prime_combs)

    min_diff = 10000

    answer = ()
    for prime_comb in prime_combs:
        n1, n2 = sorted(prime_comb)
        if n1 + n2 == n:
            if n2 - n1 < min_diff:
                answer = (n1, n2)

    print(f"{answer[0]} {answer[1]}")

결과는 시간초과....

시간초과를 해결하기 위해 에라토스테네스의 체를 사용해봤다.

에라토스테네스의 체는 임의의 자연수 n에 대해 그 이하의 소수를 찾는 가장 간단하고 빠른 방법인데, for문을 돌면서 소수의 배수들을 삭제 시키는 식으로 동작한다. 자세한 건 아래 링크를 참고하면 된다.

https://wikidocs.net/21638

그래서 get_primes 부분을 에라토스테네스의 체를 이용한 방식으로 변경해봤다.

def get_primes(n):
    primes = []
    sieves = [True] * (n + 1)

    for i in range(2, n):
        if sieves[i]:
            for j in range(i * 2, n, i):
                if sieves[j]:
                    sieves[j] = False

    primes = [idx for idx in range(2, n) if sieves[idx] == True]

    return primes

근데 결과는 그래도 시간초과였다.... 🤯

아무래도 전체 조합을 다 구하는 데에서 시간초과가 난 거 같아서 다른 방법을 생각해 보기로 한다

엄청 쉬운 방법이 있었다!
수를 반으로 나눈 나음에 하나는 1씩 올리고 하나는 1씩 내리면서 그 두 수가 모두 소수면 그걸 출력하고 break를 거는 방법

최종 코드



t = int(input())


def isPrime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True


for i in range(t):
    n = int(input())

    n1, n2 = n // 2, n // 2

    while True:
        if isPrime(n1) and isPrime(n2):
            print(f"{n1} {n2}")
            break

        n1 -= 1
        n2 += 1

결과는 통과
결국 에라토스테네스의 체는 필요가 없었다..

그래도 에라토스테네스의 채에 대해서 한 번 더 배울 수 있었고, 두 수의 차이가 최소가 되면서 합은 n으로 일정하게 유지하는 방법에 대한 아이디어를 얻을 수 있어서 좋았다.

profile
개발자

0개의 댓글