백준_9020: 골드바흐의 추측

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

9020번: 골드바흐의 추측

 

 

내 코드:

import sys
n = int(input())
nums = []
for i in range(n):
    nums.append(int(sys.stdin.readline()))

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

for target in nums:
    for x in range(target//2, 1, -1):
        if isPrime(x) and isPrime(target-x):
            print(x, target-x)
            break

맞게 나왔지만 상당히 비효율적인 것 같다.

 

Best Code:

sosu = [0 for i in range(10001)]
sosu[1] = 1
for i in range(2, 10001):
    for j in range(i * 2, 10001, i):
        sosu[j] = 1 # 소수가 아니므로 1 넣기
        
t = int(input())

for i in range(t):
    a = int(input())
    b = a // 2
    for j in range(b, 1, -1):
        if sosu[a - j] == 0 and sosu[j] == 0:
            print(j, a - j)
            break

 

포인트:

1. 소수 판별시에는 '에라토스테네스의 체'를 활용하자!! -> 시간복잡도가 1/7배로 줄어든다.

 

 

에라토스테네스의 체란?

https://ko.wikipedia.org/wiki/에라토스테네스의_체

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

위 위키백과에 잘 나와있듯이,

2부터 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수들 중에서 차례대로 자기 자신ㅇ르 제외한 배수들을 모두 지우면 된다.

 

 

참고:

https://pacific-ocean.tistory.com/129

[백준] 9020번(python 파이썬)