[파이썬]백준 17103 골드바흐파티션

링크

백준 17103 골드바흐파티션

이전에 에라토스테네스의 체를 공부한 것은 이 문제를 풀기 위함이었다.
풀긴풀었으나 속도가 너무너무 느리다.

에라토스테네스의 체를 사용해 최대 입력값인 1,000,000 까지의 소수들을 계산해 리스트를 만들었다.

그 후 해당 리스트와 에라토스테네스에서 체로 사용한 리스트를 사용해 더해서 소수인지 판별해 주었다.

좀 더 자세히 설명하자면,

소수1 + 소수2 = N 이므로 N - 소수1 = 소수2이다.
1. 소수만 담긴 리스트를 반복해서 뽑아낸다.
2. N - 뽑아낸 소수
3. 위에서 계산된 값을 sieve리스트에 인덱스 값으로 사용해 True인지 False인지 판단
4. 만약 뽑아낸 소수가 N - 뽑아낸 소수보다 클경우 break (이 이후론 순서만 바뀐 같은 수 )

숫자와 인덱스를 매치시켜 소수판별만 하는 리스트를 반복시키는 것 보다 해당 방법이 아주 조금 계산이 줄어드는 것 같다. (시간초과나던데..?)

그래도 여전히 느린데 어떻게 더 빠르게 계산할 수 있을지 생각해봐야겠다 ㅜㅠ

정답 코드

prime_arr = []
sieve = [False, False] + ([True] * (1000000 - 1))
for i in range(2, 1000001):
    if sieve[i]:
        prime_arr.append(i)
    for j in range(i * 2, 1000001, i):
        sieve[j] = False

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

    N = int(input())
    cnt = 0
    for i in range(len(prime_arr)):
        if prime_arr[i] > N - prime_arr[i]:
            break
        if sieve[N - prime_arr[i]]:
            cnt += 1
    ans.append(cnt)

print(*ans, sep='\n')

알게된 것👨‍💻

• 소수판별법