fork(1) download
copy 
  1. try: from sympy import factorint
  2. except ImportError: factorint = None
  3.  
  4. try: range = xrange
  5. except NameError: pass
  6.  
  7. try: from tqdm import trange
  8. except ImportError: trange = range
  9.  
  10.  
  11. from collections import Counter
  12.  
  13.  
  14. def multiplicity(n, p):
  15.     i = 0
  16.     while not n % p:
  17.         i += 1
  18.         n = n // p
  19.     return i
  20.  
  21. def min_factorial(prime, mult):
  22.     cnt = 0
  23.  
  24.     for i in range(1, mult + 1):
  25.         cnt += multiplicity(i, prime)
  26.  
  27.         if cnt + i >= mult:
  28.             return prime * i
  29.  
  30.  
  31. def min_factorials_sum(m, n, factorize):
  32.     s = 0
  33.  
  34.     for x in trange(m, n + 1):
  35.         factors = factorize(x)
  36.         s += max(min_factorial(p, m) for p, m in factors.items())
  37.  
  38.     return s
  39.  
  40.  
  41. def factorize(n):
  42.     factors = []
  43.     d = 2
  44.  
  45.     while d * d <= n:
  46.         while (n % d) == 0:
  47.             factors.append(d)
  48.             n //= d
  49.         d += 1
  50.  
  51.     if n > 1:
  52.        factors.append(n)
  53.  
  54.     return Counter(factors)
  55.  
  56.  
  57. m, n = 6, 10
  58. result = min_factorials_sum(m, n, factorint or factorize)
  59. print(result)
  60.  
Success #stdin #stdout 0.02s 10248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
25
https://ideone.com/g6Wn5O
language:
Python 3 (python  3.9.5)
created:
7 years ago
visibility:
public

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!