試し割り

$2$ から $\sqrt{N}$ までの数で割ってみる方法です。篩を作るほどではないときや、 $N$ が $10^{12}$ 程度まで大きいときに使います。

• is_prime(n): $n$ が素数か。 $O(\sqrt{n})$
• divisors(n): $n$ の約数を昇順で返す（ $n \ge 1$）。 $O(\sqrt{n})$
• factorize(n): [(素因数, 指数), ...] を素因数の昇順で返す（ $n \ge 1$）。 $O(\sqrt{n})$

$N$ 以下の数を何度も扱うときは、エラトステネスの篩 の方が速いです。

コード

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return True


def divisors(n):
    small = []
    large = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            small.append(i)
            if i != n // i:
                large.append(n // i)
        i += 1
    return small + large[::-1]


def factorize(n):
    # [(素因数, 指数), ...]
    res = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            e = 0
            while n % i == 0:
                n //= i
                e += 1
            res.append((i, e))
        i += 1
    if n > 1:
        res.append((n, 1))
    return res