fork download 
  1. import math
  2.  
  3. MAX_SUM = 73
  4. prime = [True for i in range(MAX_SUM)]
  5.  
  6.  
  7. def sieve():
  8.     prime[0] = prime[1] = False
  9.     for i in range(2, int(math.sqrt(MAX_SUM))):
  10.         if prime[i]:
  11.             for j in range(i * i, MAX_SUM, i):
  12.                 prime[j] = False
  13.  
  14.  
  15. def compute_digits_list(n):
  16.     digits = []
  17.     while n > 0:
  18.         digits.append(n % 10)
  19.         n //= 10
  20.  
  21.     digits.reverse()
  22.     return digits
  23.  
  24.  
  25. def compute_digit_dp(n):
  26.     digits = compute_digits_list(n)
  27.  
  28.     digit_dp = [[[0 for k in range(2)] for j in range(MAX_SUM)] for i in range(len(digits))]
  29.  
  30.     for i in range(digits[0]):
  31.         digit_dp[0][i][1] = 1
  32.  
  33.     digit_dp[0][digits[0]][0] = 1
  34.  
  35.     for i in range(1, len(digits)):
  36.         for j in range(0, 10):
  37.             for sum in range(j, MAX_SUM):
  38.                 digit_dp[i][sum][1] += digit_dp[i - 1][sum - j][1]
  39.                 if j < digits[i]:
  40.                     digit_dp[i][sum][1] += digit_dp[i - 1][sum - j][0]
  41.  
  42.                 if j == digits[i]:
  43.                     digit_dp[i][sum][0] += digit_dp[i - 1][sum - j][0]
  44.  
  45.     return digit_dp
  46.  
  47.  
  48. def compute_g_one_numbers(n):
  49.     if n < 2:
  50.         return 0
  51.  
  52.     g_one_nums = 0
  53.  
  54.     digit_dp = compute_digit_dp(n)
  55.  
  56.     for sum in range(0, MAX_SUM):
  57.         if prime[sum]:
  58.             for isLessThan in range(2):
  59.                 g_one_nums += digit_dp[len(digit_dp) - 1][sum][isLessThan]
  60.  
  61.     return g_one_nums
  62.  
  63.  
  64. def main_program():
  65.     sieve()
  66.     test_cases = int(input())
  67.     while test_cases > 0:
  68.         start, end = map(int, input().split())
  69.         print(compute_g_one_numbers(end) - compute_g_one_numbers(start - 1))
  70.         test_cases -= 1
  71.  
  72.  
  73. if __name__ == '__main__':
  74.     main_program()
  75.  
Success #stdin #stdout 0.02s 9572KB
comments (?)
stdin 
3
10 19
1 9
20 29
stdout 
4
4
5
https://ideone.com/m6Aa4Q
language:
Python 3 nbc (python 3.7.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!