Project-Euler-Problem-46.md

prime_sieve()

def prime_sieve(n):
    sieve = [True] * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]

from collections import defaultdict
gx = defaultdict(int)
primes = prime_sieve(500005)
sq2 = [2*i*i for i in range(1,500)]

for p in primes:
    for sqx2 in sq2:
        g = p + sqx2
        if g > 500000: break
        gx[g]+= 1

for _ in range(int(input())):
    n = int(input())
    print (gx[n])