Guest User

Factorial, the funny way

a guest
Jun 9th, 2020
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.17 KB | None | 0 0
  1. import math
  2. from collections import defaultdict
  3. from copy import copy
  4.  
  5.  
  6. def eratosthenes(n):
  7.     sieve = set(range(2, n + 1))
  8.     for p in range(2, int(math.sqrt(n)) + 1):
  9.         if p in sieve:
  10.             d = 2 * p
  11.             while d <= n:
  12.                 try:
  13.                     sieve.remove(d)
  14.                 except KeyError:
  15.                     pass
  16.                 d += p
  17.     return sieve
  18.  
  19.  
  20. def get_prime_factor_freq(l, max, res, n=None, nfactors=None):
  21.     n = 1 if n is None else n
  22.     nfactors = defaultdict(int) if nfactors is None else nfactors
  23.  
  24.     r = copy(l)
  25.     for e in l:
  26.         r.remove(e)
  27.         d = n
  28.         dfactors = copy(nfactors)
  29.         exp = 0
  30.  
  31.         d *= e
  32.         while d <= max:
  33.             dfactors[e] += 1
  34.             exp += 1
  35.  
  36.             res[e] += exp
  37.             for x, y in nfactors.items():
  38.                 res[x] += y
  39.  
  40.             get_prime_factor_freq(r, max, res, d, dfactors)
  41.             d *= e
  42.  
  43.  
  44. def factorial(n):
  45.     a = eratosthenes(n)
  46.  
  47.     r = defaultdict(int)
  48.     get_prime_factor_freq(a, n, r)
  49.  
  50.     res = 1
  51.     for x, y in r.items():
  52.         res *= x ** y
  53.     return res
  54.  
  55.  
  56. print(factorial(50))
Add Comment
Please, Sign In to add comment