even_ratio.py

even_ratio.py

import collections
import functools
import sys
import typing


@functools.cache
def __prime_factorize(i: int, f: int) -> tuple[int, ...]:
    if i < f:
        return ()
    if i % f == 0:
        return (f,) + __prime_factorize(i // f, 2)
    return __prime_factorize(i, f + 1)


def prime_factorize(n: int) -> tuple[int, ...]:
    return __prime_factorize(n, 2)


def counting_prime_factorize(n: int) -> dict[int, int]:
    prime_factors = prime_factorize(n)
    c = collections.Counter()
    for p in prime_factors:
        c[p] += 1
    return dict(c)


def __ratio(n: int) -> dict[int, float]:
    factors = {base: base ** count for base, count in counting_prime_factorize(n).items()}
    sum_of_factors = sum(factors.values())    
    return {n: factor / sum_of_factors for n, factor in factors.items()}


def even_ratio(n: int) -> float:
    return __ratio(n).get(2, 0)


def main() -> None:
    n = 1000
    print("数\t偶数度")
    sys.setrecursionlimit(n * 10)
    for n in range(1, n):
        ratio = even_ratio(n)
        print(f"{n}\t{ratio:.0%}")


if __name__ == "__main__":
    main()