골드바흐 파티션

• 먼저 1,000,000 이하의 소수 목록을 미리 구해서 set에 저장해 둔다.
• 그러면, 각각의 N에 대해서 합이 N이 되는 소수 쌍의 갯수를 찾는 것은, 모든 소수 Pi를 순회하면서 N-Pi가 소수 목록에 포함되는지를 체크해서 그 갯수를 세면 된다.
• 이렇게 구해진 소수 쌍의 갯수에는 순서만 다른 소수쌍도 포함되므로 이것을 보정하기 위해서 결과값을 2로 나눠서 출력해야 한다. 이때, 같은 소수가 두번 더해져서 얻어진 경우가 포함된 경우를 또 따로 고려해줘야 한다. 같은 소수를 두번 더해서도 N이 만들어질 수 있다면, 그 경우에는 카운트가 홀수로 나올 것이다. 그리고 출력할 값은 (카운트 - 1)/2 + 1 = 카운트/2 + 0.5가 되므로, 결국 그냥 모든 경우에 대해서 카운트/2 를 반올림한 값을 출력하면 된다.
  • 반올림을 할 때 python의 round로는 의도한 결과가 안나온다. sum(divmod(count,2))로 처리했다.
• 소수 목록을 구하는 데에 O(nloglogn), 각각의 쿼리마다 모든 소수를 한번씩 순회해야 하고, 소수의 갯수는 O(n/logn)이니까, t개의 쿼리를 처리하는 것은 O(tn/logn). 합치면 O(nloglogn + tn/logn)

"""Solution code for "BOJ 17103. 골드바흐 파티션".

- Problem link: https://www.acmicpc.net/problem/17103
- Solution link: http://www.teferi.net/ps/problems/boj/17103
"""

from teflib import numtheory


def main():
    T = int(input())
    N = [int(input()) for _ in range(T)]
    primes = set(numtheory.prime_list(max(N)))
    for n_i in N:
        count = sum(1 for p in primes if n_i - p in primes)
        print(sum(divmod(count, 2)))


if __name__ == '__main__':
    main()

• Dependency: teflib.numtheory.prime_list