Problem:
Problem A: Sum of Consecutive Prime Numbers Some positive integers can be represented by a sum of one or more consecutive prime numbers.
How many such representations does a given positive integer have? For example, the integer 53
has two representations 5 + 7 + 11 + 13 + 17 and 53. The integer 41 has three representations
2 + 3 + 5 + 7 + 11 + 13, 11 + 13 + 17, and 41. The integer 3 has only one representation, which is
3. The integer 20 has no such representations. Note that summands must be consecutive prime
numbers, so neither 7 + 13 nor 3 + 5 + 5 + 7 is a valid representation for the integer 20. Your mission is to write a program that reports the number of representations for the given
positive integer. Input The input is a sequence of positive integers each in a separate line. The integers are between 2
and 10 000, inclusive. The end of the input is indicated by a zero. Output The output should be composed of lines each corresponding to an input line except the last zero.
An output line includes the number of representations for the input integer as the sum of one
or more consecutive prime numbers. No other characters should be inserted in the output. Sample Input 2
3
17
41
20
666
12
53
0 Output for the Sample Input 1
1
2
3
0
0
1
2

Solution (Python):
import math
primes = []
for p in range(2,10001):
    for m in range(2,math.floor(math.sqrt(p)) + 1):
        if p % m == 0:
            break
    else:
        primes.append(p)
targ = int(input())
while targ != 0:
    ans = 0
    for p in range(len(primes)):
        if primes[p] > targ:
            break
        tempsum = 0
        for l in range(p,len(primes)):
            tempsum += primes[l]
            if tempsum > targ:
                break
            elif tempsum == targ:
                ans += 1
                break
    print(ans)
    targ = int(input())

Solution (Python):
p=[]
a=[0]*2+[1]*10001
for i in range(2,int(10000**0.5)+1):
    if a[i]:
        for j in range(i*i,10001,i):
            a[j]=0
for i in range(2,10001):
    if a[i]:p+=[i]
b=[0]*5736397
for i in range(len(p)):
    c=0
    for j in range(i,len(p)):
        c+=p[j]
        b[c]+=1
while 1:
    n=int(input())
    if n==0:break
    print(b[n])

Solution (Python):
p=[]
for i in range(2,10001):
        for j in range(2,int(i**0.5)+1):
            if not i%j:break
        else:p+=[i]
b=[0]*5736397
for i in range(len(p)):
    c=0
    for j in range(i,len(p)):
        c+=p[j]
        b[c]+=1
while 1:
    n=int(input())
    if n==0:break
    print(b[n])

Solution (Python):
primes = [0, 0] + [1]*9999
for i in range(2, 101):
    if primes[i]:
        for j in range(i*i, 10001, i):
            primes[j] = 0
while True:
    n = int(input())
    if n == 0:
        break
    m = n
    while not primes[m]:
        m -= 1
    pnum = [i for i in range(m+1) if primes[i]]
    ans = 0
    for i in range(len(pnum)):
        tmp = 0
        for j in range(i, len(pnum)):
            tmp += pnum[j]
            if tmp == n:
                ans += 1
                break
            if tmp > n:
                break
    print(ans)

Solution (Python):
primes = [0, 0] + [1]*9999
for i in range(2, 101):
    if primes[i]:
        for j in range(i*i, 10001, i):
            primes[j] = 0
pnums = [i for i in range(10001) if primes[i]]
while True:
    n = int(input())
    if n == 0:
        break
    m = n
    while not primes[m]:
        m -= 1
    ans = 0
    end = pnums.index(m)+1
    for i in range(end):
        tmp = 0
        for j in range(i, end):
            tmp += pnums[j]
            if tmp == n:
                ans += 1
                break
            if tmp > n:
                break
    print(ans)

Solution (Python):
import sys

prime_table=[i for i in range(10010)]
prime_table[1]=0

for i in range(2,101):
    if prime_table[i]==i:
        k=2
        while k*i<10010:
            prime_table[k*i]=0
            k+=1

sum_list=[0]
k=0
for i in prime_table:
    if i!=0:
        k+=i
        sum_list.append(k)


while True:
    n=int(input())
    if n==0:
        sys.exit()
    count=0
    for i in sum_list:
        if i-n in sum_list:
            count+=1
    print(count)

Solution (Python):
import math
isPrime = [1 for _ in range (10002)]
isPrime[:2] = [0, 0]
for i in range(2, 101):
    for j in range(i*i, 10001, i):
        isPrime[j] = 0
prime = []
for i in range(10001):
    if isPrime[i] == 1:
        prime.append(i)
while True:
    n = int(input())
    if n == 0:
        break
    cnt = 0
    for i in range(len(prime) + 1):
        sum = 0
        for j in range(i,len(prime)):
            sum += prime[j]
            if sum == n:
                cnt += 1
                break
            if sum > n:
                break
    print(cnt)

Solution (Python):
ps = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973,1000000]




from queue import Queue

while(True):
    n = int(input())
    ans = 0
    if n == 0:
        quit()
    lis = Queue()
    nowsum = 0
    for i in ps:
        while(nowsum > n):
            x = lis.get()
            nowsum -= x
        if nowsum == n:
            ans += 1
        lis.put(i)
        nowsum += i
    print(ans)

Solution (Python):
def sieve(MAX):
    list=[True]*(MAX+1)
    prime=[]
    for i in range(2,MAX+1):
        if list[i]:
            prime.append(i)
            for j in range(i,MAX+1,i):  list[j]=False
    return prime

def main():
    prime=sieve(10000)
    while True:
        N=int(raw_input())
        if(N==0):   break
        ans=0
        for i in range(len(prime)):
            if prime[i]>=N:
                if prime[i]==N: ans+=1
                break
            tmp=prime[i]
            for j in range(i+1,len(prime)):
                tmp+=prime[j]
                if tmp>=N:
                    if tmp==N:  ans+=1
                    break
        print ans

if __name__=='__main__':    main();

Solution (Python):
r = 100001
p = [1]*r
p[0] = p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0 for x in range(2*i,r,i)]
prime = []
for i in range(r):
	if p[i]: prime.append(i)
	
while 1:
	n = int(raw_input())
	if n == 0: break
	ans = 0
	i = 0
	while 1:
		s = 0
		j = i
		while 1:
			s += prime[j]
			if s >= n:
				if s == n:
					ans += 1
				break
			j += 1
		i += 1
		if prime[i] > n: break
	print ans

Solution (Python):
from collections import defaultdict


class Primes():
    def __init__(self, N):
        self.N = N
        self.prime = {i for i in range(2, self.N+1)}
        for i in range(2, self.N+1):
            if i in self.prime:
                for j in range(i*2, self.N+1, i):
                    if j in self.prime:
                        self.prime.remove(j)

    def show_primes(self):
        return sorted(list(self.prime))


def main():
    D = defaultdict(int)
    P = Primes(10000)
    prime = P.show_primes()
    prime.insert(0, 0)
    L = len(prime)
    for i in range(1, L):
        prime[i] += prime[i-1]
    
    for i in range(L):
        for j in range(i+1, L):
            D[prime[j]-prime[i]] += 1
            
    
    V = 1
    while V != 0:
        V = int(input())
        if V==0:
            continue
        print(D[V])
    return


if __name__ == "__main__":
    main()

Solution (Python):


"""
Problems 1257
Problem A: Sum of Consecutive Prime Numbers
"""
import math
def eratosthenes(n):
    """
    エラトステネスのふるい
    """
    primes = [i for i in range(n)]
    primes[1] = 0 
    for prime in primes:
        if prime > math.sqrt(n):
            break
        if prime == 0:
            continue
        for non_prime in range(2 * prime, n, prime): 
            primes[non_prime] = 0 
    prime_list = []
    for prime in primes:
        if prime != 0:
            prime_list.append(prime)
    return prime_list


primes = eratosthenes(11000)
while True:
    n = int(input())
    if n == 0:
        break
    r = 1
    ans = 0
    for i in range(len(primes)): 
        if n <= primes[i]: 
            r = i + 1
            break
    for i in range(r):
        sum = 0
        for j in range(i, r):
            sum += primes[j]
            if n == sum:
                ans += 1
                break
            if sum > n:
                break
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def sieve(n):
    if n == 1:return []
    primes = [1 if i%2 == 1 else 0 for i in range(n + 1)]
    primes[1] = 0
    primes[2] = 1
    for i in range(3,n + 1,2):
        if i * i > n:
            break
        if primes[i]:
            for j in range(i * i,n + 1,i):
                primes[j] = 0
    return [p for p in range(2,n + 1) if primes[p] == 1]

primes = sieve(10005)
P = len(primes)

def solve(N):
    ans = 0
    r = 0
    tot = 0
    for l in range(P):
        if primes[l] > N:
            break
        while r < P and tot + primes[r] <= N:
            tot += primes[r]
            r += 1
        if tot == N:
            ans += 1
        tot -= primes[l]
    print(ans)

while True:
    N = int(input())
    if N == 0:
        exit()
    solve(N)

Solution (Python):
"""
Problem A: Sum of Consecutive Prime Numbers
https://onlinejudge.u-aizu.ac.jp/problems/1257
input : 2 < n < 10000

"""
def prime_list(n):
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1 ):
        if not is_prime[i]:
            continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

def subset_sum_problem(prime_list, length):

    subset_dict = {}
    for i in range(length):
        now = 0
        for j in range(i, length):
            now += prime_list[j]
            if not now in subset_dict:
                subset_dict[now] = 1
            else:
                subset_dict[now] = subset_dict[now] + 1

    return subset_dict

if __name__ == '__main__':
    prime_list = prime_list(10000)
    length = len(prime_list)
    subset_dict = subset_sum_problem(prime_list, length)
    ans = []
    while(True):
        n = int(input())
        if n == 0:
            break
        if not n in subset_dict:
            ans.append(0)
        else:
            ans.append(subset_dict[n])

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

Solution (Python):
def prime(n):
    prime_flag = [0 for i in range(n + 1)]
    prime_list = []
    for i in range(2, n + 1):
        if prime_flag[i] == 0:
            prime_list.append(i)

            temp = 1
            while temp * i <= n:
                prime_flag[temp * i] = 1
                temp += 1
    return prime_list


prime_list = prime(10000)

answer = []

while True:
    n = int(input())
    if not n:
        break
    left = 0
    right = 0
    count = 2
    ans = 0
    while True:
        if n == count:
            ans += 1

        if left == right == len(prime_list) - 1:
            break
        elif count + prime_list[right + 1] <= n and right != len(prime_list) - 1:
            right += 1
            count += prime_list[right]
        else:
            if left == right:
                left += 1
                right += 1
                count = prime_list[left]
            else:
                count -= prime_list[left]
                left += 1

    answer.append(ans)

for i in answer:
    print(i)

Solution (Python):

def Eratosthenes(N):
    ans = [True for i in range(N + 1)]
    ans[0], ans[1] = False, False
    
    for i in range(int(N ** (1 / 2)) + 1):
        if ans[i]:
            for j in range(2 * i, N, i):
                ans[j] = False
    
    return [i for i in range(N + 1) if ans[i]]


def Cumulative_sum(lists):
    ans = [0]
    for i in lists:
        ans.append(ans[-1] + i)
    return ans

ans = []
while True:
    N = int(input())
    if not N:
        break
    
    prime_sum = Cumulative_sum(Eratosthenes(N + 10))
    left, right = 0, 1
    tmp_ans = 0
        
    while left != right:
        
        if prime_sum[right] - prime_sum[left] == N:
            tmp_ans += 1
            right += 1
        
        elif prime_sum[right] - prime_sum[left] > N:
            left += 1
        
        else:
            right += 1
    
    ans.append(tmp_ans)    


[print(i) for i in ans]

Solution (Python):
def sieve():
    L = 50000
    primes = []
    isPrime = [ True for _ in range(L) ]
    for i in range(2, L):
        if isPrime[i]:
            primes.append(i)
            for j in range(i*i, L, i):
                isPrime[j] = False
    return primes

def isConsecutivePrime(num, idx, primes):
    p = 0
    while True:
        p += primes[idx]
        if p == num:
            return True
        if p > num:
            return False
        idx += 1

def countConsecutivePrimes(num, primes):
    count = 0
    for i in range(len(primes)):
        if isConsecutivePrime(num, i, primes):
            count += 1
    return count

if __name__ == '__main__':
    primes = sieve()
    while True:
        num = int(input())
        if num == 0:
            break
        print(countConsecutivePrimes(num, primes))

Solution (Python):
def solve():
    
    primes = [2, 3]
    for n in range(5, 10000, 2):
        l = n ** 0.5
        for p in primes:
            if n % p == 0:
                break
            if l < p:
                primes.append(n)
                break
    
    primes = [0] + primes
    
    from itertools import accumulate
    ac_primes = list(accumulate(primes))
    
    from bisect import bisect_left, bisect_right
    from sys import stdin
    file_input = stdin
    for line in file_input:
        n = int(line)
        if n == 0:
            break
        
        low = bisect_left(ac_primes, n)
        high = bisect_right(primes, n)
        
        ans = 0
        
        for x in ac_primes[low:high]:
            t = x - n
            if t == ac_primes[bisect_left(ac_primes, t)]:
                ans += 1
        
        print(ans)

solve()