Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import math
- from collections import defaultdict
- from copy import copy
- def eratosthenes(n):
- sieve = set(range(2, n + 1))
- for p in range(2, int(math.sqrt(n)) + 1):
- if p in sieve:
- d = 2 * p
- while d <= n:
- try:
- sieve.remove(d)
- except KeyError:
- pass
- d += p
- return sieve
- def get_prime_factor_freq(l, max, res, n=None, nfactors=None):
- n = 1 if n is None else n
- nfactors = defaultdict(int) if nfactors is None else nfactors
- r = copy(l)
- for e in l:
- r.remove(e)
- d = n
- dfactors = copy(nfactors)
- exp = 0
- d *= e
- while d <= max:
- dfactors[e] += 1
- exp += 1
- res[e] += exp
- for x, y in nfactors.items():
- res[x] += y
- get_prime_factor_freq(r, max, res, d, dfactors)
- d *= e
- def factorial(n):
- a = eratosthenes(n)
- r = defaultdict(int)
- get_prime_factor_freq(a, n, r)
- res = 1
- for x, y in r.items():
- res *= x ** y
- return res
- print(factorial(50))
Add Comment
Please, Sign In to add comment