Goldbach’s conjecture

Brute force

# prime_list는 1부터 10000사이의 소수가 오름차순으로 저장된 리스트예요.
from prime import prime_list
import math

def is_prime(x):
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False 
    return True

# 합계가 짝수가 되는 두 소수를 찾는 함수예요.
def goldbach(arr):
    # 합계가 짝수가 되는 두 소수를 작은 수부터 차례로 리스트에 저장해 주세요.
    answer = []
    for n in arr:
        i = 0
        ex = []
        while (prime_list[i] <= n //2):
            diff = n - prime_list[i];
            if diff in prime_list:
                ex.append([prime_list[i], diff])
            i += 1
        answer.append(ex)
    final_answer = []
    for a in answer:
        final_answer.append(a[-1])
    return final_answer

arr = [int(x) for x in input().split()]

for i in goldbach(arr):
    print(i[0], i[1])

• 소수리스트가 주어져있을때, 소수리스트의 작은 원소를 기준으로 두고, 그 기준과 원소의 차이를 구해서 그 차이가 소수인지 확인하는 작업을 통해 구한다. 다만, 소수가 확인하는 작업을 할때, 시간이 많이 걸리는것 같고
• 도대체 어디서 시간이 그렇게 많이 걸릴까???
• 정석풀이는 10000개의 크기의 배열을 선언하고, 이 10000개의 배열에 소수인지 아닌지 마킹한다. 그래서, O(1)의 시간으로 바로바로 소수인지 아닌지 확인할 수 있는데, 나는 diff in prime_list 에서 시간이 정말 많이 걸리는것 같다. 만약, 배열을 선언하고 바로바로 소수인지 확인했으면 시간이 덜 걸렸을 텐데, 이 엘리스에서 요구하는 조건을 사용하다 보니까 시간이 .. ㅋㅋㅋ 안습이다.