[Baekjoon] 9020번 : 골드바흐의 추측 (Python, 소수)

[Baekjoon] 9020번 : 골드바흐의 추측 (Python, 소수)

 

목차

 

 

 

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

9020번: 골드바흐의 추측

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 - 메모리 116324KB / 시간 4192ms / 코드 길이 454B (PyPy3 통과)

 

def prime(k):
    if k == 1:
        return 0

    for i in range(2, int(k ** 0.5) + 1):
        if k % i == 0:
            return 0
    return 1

prime_list = []

for i in range(2, 10000+1):
    if prime(i):
        prime_list.append(i)

for i in range(int(input())):
    ans = []
    n = int(input())

    for j in prime_list:
        if n - j in prime_list:
            ans.append((abs(j-(n-j)), j, n-j))
    ans.sort()
    print(ans[0][1], ans[0][2])

 

방법 2 - 메모리 30840KB / 시간 788ms / 코드 길이 324B

 

절반에 대하여 하나씩 감소하며 소수를 찾는 방법

2 소수의 차이가 작은 것부터 찾으라고 하여 절반부터 하나씩 차이를 주며 결과를 도출하는 방법임

 

def prime(k):
    if k == 1:
        return 0

    for i in range(2, int(k ** 0.5) + 1):
        if k % i == 0:
            return 0
    return 1

for i in range(int(input())):
    ans = []
    n = int(input())

    for j in range(n//2, 0, -1):
        if prime(j) and prime(n-j):
            print(j, n-j)
            break