素因数分解、約数列挙

def prime_decomposition(n):
    table = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            table += [i]
            n //= i
        if n == 1:
            break
    if n != 1:
        table += [n]
　　　# 素数の場合
    return table

素因数分解したリストを返すプログラム。

こちらは約数列挙。競プロでは必須である。まず、リストで欲しい場合。

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors += [i]
            if i != n // i:
                divisors += [n // i]

    # divisors.sort()
    return divisors

setで欲しい場合はこちら。

def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return divisors # sortしたリストで欲しい時はsorted(divisors)