Doing some katas, prime factorization of n! is once again a small fun problem to have a go at. I wonder how many equal solutions are out there :) anyway, creating a max prime divisor map instead of the standard Eratosthenes' was an interesting twist of mine (?) so I thought I'd capture it. For the betterment of my audience of 0 people I guess : ))
from collections import Counter
from typing import Dict, List, Tuple
from functools import lru_cache
import math
def max_prime_divisors(n) -> List[int]:
# A slight variation of Erathosthenes' algorithm
# Find and return max_prime_divisor[i], i = 0..n
# true divisors: 1 and n itself are excluded
# could be nicer with numpy arrays? :)
ans = [None] * (n + 1)
for k in range(2, len(ans) // 2 + 1):
if ans[k] is None:
i = k * 2
while i < len(ans):
ans[i] = k
i += k
return ans
def decomp_nr(n, mpd) -> Dict[int, int]:
# return value is in prime -> count form
ans = []
while mpd[n]:
d = mpd[n]
ans.append(d)
n = n // d
if n >= 1:
ans.append(n)
return Counter(ans)
def format_decomp(d):
factors = [f"{key}^{count}" if count > 1 else f"{key}"
for key, count in sorted(d.items())]
return " * ".join(factors)
def decomp(n):
# decompose factorial
mpd = max_prime_divisors(n)
total_decomp = sum([decomp_nr(k, mpd) for k in range(2, n + 1)], Counter())
# print("tdc is:", total_decomp)
return format_decomp(total_decomp)
---
Update: hm... and despite its appeal to me, that wasn't fast enough :) then went the one with much fewer tiny reusable cogs, and sorted things out.
I'll decide later whether to decide now or later that I'm disappointed. Possibly I'm not :)
---
from collections import Counter
from typing import Dict, List, Tuple, Optional
from functools import lru_cache
import math
def erathosthenes(n) -> List[bool]:
# return is_prime[i], i = 0..n
ans = [True] * (n + 1)
# by convention
ans[0] = False
ans[1] = False
for k in range(2, len(ans) // 2 + 1):
if ans[k]:
i = k * 2
while i < len(ans):
ans[i] = False
i += k
return ans
def decomp_n_fac(n, erat: List[bool]) -> Dict[int, int]:
ans = {}
for p in range(n + 1):
exp = 0
if not erat[p]:
continue
p_pow = p
while p_pow <= n:
exp += n // p_pow
p_pow *= p
ans[p] = exp
return ans
def format_decomp(d):
factors = [f"{key}^{count}" if count > 1 else f"{key}"
for key, count in sorted(d.items())]
return " * ".join(factors)
def decomp(n):
# decompose factorial
erat_map = erathosthenes(n)
total_decomp = decomp_n_fac(n, erat_map)
return format_decomp(total_decomp)
