python3 高效實作 最大質因數/質因數集合 方法

def gcd(a, b):
    """
    greatest common divisor  # https://baike.baidu.com/item/歐幾裡得算法
    :param a: int
    :param b: int
    :return:
    """
    while b > 0:
        d = a % b
        a = b
        b = d
    return a


def ggf(n):
    """
    general Qualitative factors 生成質因數集合，第i個元素為i的質因數set，并剔除了1(為了節省記憶體)
    :param n:
    :return:
    """
    ret_li = [{0}, set(), {2}]
    for i in range(3, n+1):
        ret_li.append(set())  # append的既是ret_li[i]
        for j in range(2, int(i**.5) + 1):
            d, m = divmod(i, j)
            if m == 0:
                ret_li[i] = ret_li[d] | {j}
                break
        if len(ret_li[i]) == 0:
            ret_li[i] = {i}
    return ret_li


def gf_ic(n, c_di=None):
    """
    Qualitative factors use iter with cache dict ,直接修改傳入的c_di, 沒有結合ggf來獲得c_di
    想加速還可以注釋掉所有 if c_di is None的情況, 且保證一定傳入c_di
    :param n:
    :param c_di:
    :return: c_di[n]
    """
    # if c_di is None:
    #     gfs_20 = ggf(20)
    #     c_di = {i: gfs_20[i] for i in range(1, 21)}
    if n not in c_di:
        for j in range(2, int(n ** .5) + 1):
            d, m = divmod(n, j)
            if m == 0:
                c_di[n] = gf_ic(d, c_di) | {j}
                break
    if n not in c_di:
        c_di[n] = {n}
    return c_di[n]           

通過如下代碼進行測試：

gfs_20 = ggf(20)

c_di = {i: gfs_20[i] for i in range(1, 21)}

gf_ic(20, c_di)
Out[4]: {2, 5}
gf_ic(99, c_di)
Out[5]: {3, 11}
c_di
Out[6]: 
{1: set(),
 2: {2},
 3: {3},
 4: {2},
 5: {5},
 6: {2, 3},
 7: {7},
 8: {2},
 9: {3},
 10: {2, 5},
 11: {11},
 12: {2, 3},
 13: {13},
 14: {2, 7},
 15: {3, 5},
 16: {2},
 17: {17},
 18: {2, 3},
 19: {19},
 20: {2, 5},
 33: {3, 11},
 99: {3, 11}}
gf_ic(999999999, c_di)
Out[7]: {3, 37, 333667}