CLSUMG_tester.py

import numpy as np
from scipy import signal
from collections import Counter

MAX = 10 ** 6 + 5
p = [1] * MAX
p[0] = p[1] = 0
for i in range(2, MAX):
    if i * i > MAX: break
    if p[i]:
        for j in range(i * i, MAX, i):
            p[j] = 0

f = signal.fftconvolve(p, p)
f = np.around(f + 1).astype(int) // 2

for t in range(int(input())):
    N = int(input())
    v = f[N]
    c = Counter(f[:N])
    ans = i = 0
    while 2 * i < v:
        ans += c[i] * c[v - i]
        i += 1
    if v % 2 == 0:
        v2 = v // 2
        ans += (c[v2] + 1) * c[v2] // 2;
    print(ans)