백준 - 9020번 - 골드바흐의 추측

백준 - 9020번 - 골드바흐의 추측

---

 

9020번: 골드바흐의 추측

 

틀린 코드1(시간초과)

혹시나 해서 n의 값에 따른 primes를 따로따로 구했더니 시간 초과가 되었다.

def find_primes(n):
    primes = []
    for num in range(2, n+1):
        do = 'yes'
        if num <= 3:
            primes.append(num)
        elif num % 2 != 0:
            for i in range(3, int(num**(1/2))+2, 2):
                if num % i == 0:
                    do = 'no'
                    break
            if do == 'yes':
                primes.append(num)
    return primes
T = int(input())
for i in range(T):
    n = int(input())
    primes = find_primes(n)
    for index in range(int(len(primes)/2), len(primes)):

        if n - primes[index] in primes:
            print(n-primes[index], primes[index])
            break

 

 

틀린 코드2

시간 초과를 해결하기 위해 10000이하의 소수를 다 구하여 저장해두었다.
for index in range(int(len(num_prime)/2),len(num_prime)+1): 이 부분에서
num_prime의 크기를 반으로 나누면 n/2 값 보다 작은 소수와 큰 소수로 나누어 질 것이라 생각했다.
하지만 n/2보다 큰 소수와 작은 소수의 개수가 다르기 때문에 틀렸다. 

import sys
def find_primes(n):
    primes = []
    for num in range(2, n+1):
        do = 'yes'
        if num <= 3:
            primes.append(num)
        elif num % 2 != 0:
            for i in range(3, int(num**(1/2))+2, 2):
                if num % i == 0:
                    do = 'no'
                    break
            if do == 'yes':
                primes.append(num)
    return primes

primes = find_primes(10000)
T = int(sys.stdin.readline())
for i in range(T):
    n = int(sys.stdin.readline())
    num_prime = [prime for prime in primes if prime <= n]
    for index in range(int(len(num_prime)/2),len(num_prime)+1):
        if n - primes[index] in primes:
            print(n-primes[index], primes[index])
            break

 

맞은 코드

1. 10000보다 작은 소수들을 모두 구한다.
2. n에 대한 소수의 합들중 차이가 가장 작은 값을 선택해야한다.
3. 중간에 가까운 값일 수록 차이가 가장 적다.
4. n = a + b라면 a > n/2이고 b < n/2 이므로 n/2부터 시작해서 찾는다.
5. 그리하여 n/2이상의 소수들을 high_p으로 두고 이하의 값을 low_p으로 두었다.

import sys
def find_primes(n):
    primes = []
    for num in range(2, n+1):
        do = 'yes'
        if num <= 3:
            primes.append(num)
        elif num % 2 != 0:
            for i in range(3, int(num**(1/2))+2, 2):
                if num % i == 0:
                    do = 'no'
                    break
            if do == 'yes':
                primes.append(num)
    return primes

primes = find_primes(10000)
T = int(sys.stdin.readline())
for i in range(T):
    n = int(sys.stdin.readline())
    high_p = [prime for prime in primes if (prime >= n/2) & (prime <= n)]
    low_p = [prime for prime in primes if prime <= n / 2]
    for h in high_p:
        if (n - h) in low_p:
            print(n-h, h)
            break

 

결과