f is a function such that f(x) equals the number of ways in which x can be expressed as the sum of two prime numbers.
For example f(10)=2, as 10 can be expressed as the sum of two primes in two ways: 3+7=5+5=10. More formally, f(x) is the number of pairs (a,b) and a and b are prime and a+b=x.
Given an integer N , find the number of pairs (a,b) and f(a)+f(b)=f(N).
Input:
First-line will contain T, the number of test cases. Then the test cases follow.
Each test case contains a single line of input, an integer N.
Output:
For each test case, output in a single line, the required answer.
Constraints
1≤T≤5
0≤N≤10^6
Sample Input:
3
1
5
10
Sample Output:
1
4
21
Explanation:
Case 1: f(0)=f(1)=0. So the only way to express f(1) is as f(0)+f(0).
Case 2: f(0)=f(1)=f(2)=f(3)=0, and f(4)=f(5)=1. So f(5) can be expressed as f(0)+f(4), f(1)+f(4), f(2)+f(4) and f(3)+f(4).
Input:
4
12
23
7
43
Output:
30
21
12
180
Input:
2
21
3
Output:
60
6
Input:
1
89
Output:
300
Input:
3
1111
2314
32656
Output:
70124
21605
673704
Debug the code:
import numpy as np
from scipy import signal
from collections import Count
MAX,p = 10 ** 6 + 5,[1] * (10 ** 6 + 5)
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=((np.around(signal.fftconvolve(p, p)).astype(int) )+1)//2
for t in range(int(input())):
N = int(input())
v = f[N]
c,ans,i = Count(f[:N]),0,0
while 2 * i < v:
ans = ans + c[i] * c[v - i]
i += 1
if v % 2 == 0:ans += (c[(v // 2)] + 1) ** c[(v // 2)] // 2
print(ans)
Kindly provide the answer using the below link:
Habitate