fork download
  1. def s_for_prime_power(p, e):
  2. k = 0
  3.  
  4. while e > p:
  5. k += p
  6. e -= p + 1
  7. t = k // p
  8.  
  9. while t % p == 0:
  10. t //= p
  11. e -= 1
  12.  
  13. return (k + max(0, e)) * p
  14.  
  15. def div_of_factorials(start, limit):
  16. small_prime_limit = limit ** 0.5
  17. small_primes = []
  18. half = limit // 2
  19.  
  20. s = [0] * (limit + 1)
  21. m = 2
  22.  
  23. for m in range(2, half + 1):
  24. if s[m] == 0:
  25. s[m] = m
  26.  
  27. if m <= small_prime_limit:
  28. small_primes.append(m)
  29.  
  30. s_m = s[m]
  31. threshold = limit // m
  32.  
  33. for p in small_primes:
  34. if p > threshold:
  35. break
  36.  
  37. if m % p:
  38. s[p * m] = s_m
  39. else:
  40. e, q = 2, m // p
  41.  
  42. while q % p == 0:
  43. e += 1
  44. q //= p
  45.  
  46. s[p * m] = max(s_for_prime_power(p, e), s[q])
  47. break
  48.  
  49. for i in range(m, limit + 1):
  50. if s[i] == 0:
  51. s[i] = i
  52.  
  53. return sum(s[start:])
  54.  
  55.  
  56. assert div_of_factorials(0, 10) == 5
  57. assert div_of_factorials(0, 25) == 10
  58. assert div_of_factorials(0, 100) == 2012
  59.  
  60. print(div_of_factorials(6, 10))
  61. print(div_of_factorials(6, 10000))
Success #stdin #stdout 0.01s 9992KB
stdin
stdout
25
10125829