@@ -0,0 +1,1379 @@
+from bisect import bisect_right%0D%0Aimport math%0D%0A%0D%0AN = int(input())%0D%0A%0D%0A# 1. Sieve of Eratosthenes%0D%0Atable = %5BTrue%5D * ((N // 2) + 1)%0D%0Atable%5B0%5D = False%0D%0Afor i in range(3, int(math.sqrt(N)) + 2, 2):%0D%0A    if table%5Bi // 2%5D == False:%0D%0A        continue%0D%0A    for j in range(i ** 2, len(table) * 2, i * 2):%0D%0A        table%5Bj // 2%5D = False%0D%0A%0D%0A# 2. Write a list for primes%0D%0AprimeList = %5B2%5D%0D%0Afor i in range(len(table)):%0D%0A    if table%5Bi%5D is True:%0D%0A        primeList.append(i * 2 + 1)%0D%0A%0D%0A# 3. Binary search for continuous prime list of length k which has sum N, for all the possible value of k%0D%0Aans = 0%0D%0Afor k in range(1, 1040):%0D%0A    startRange = 0%0D%0A    endRange = bisect_right(primeList, N // k + 1) - 1%0D%0A    target = (startRange + endRange) // 2%0D%0A    if endRange %3C= 0:%0D%0A        break%0D%0A    while True:%0D%0A        targetSum = sum(primeList%5Btarget:target+k%5D)%0D%0A        if targetSum == N:%0D%0A            ans += 1%0D%0A            break%0D%0A        elif targetSum %3E N:%0D%0A            endRange = target%0D%0A        else:%0D%0A            startRange = target%0D%0A        target = (startRange + endRange) // 2%0D%0A        if startRange == target or endRange == target:%0D%0A            startSum = sum(primeList%5BstartRange:startRange+k%5D)%0D%0A            endSum = sum(primeList%5BendRange:endRange+k%5D)%0D%0A            if startSum == N or endSum == N:%0D%0A                ans += 1%0D%0A            break%0D%0A    if target == 0:%0D%0A        break%0D%0A%0D%0Aprint(ans)

solve problem no.1644