クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-6 素数判定」(p.110)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-6 素数判定」(p.110)
のコードをPythonで書き直したものとなっています。

入力


n

入力例



295927


素数判定（O(√n)）

# 素数判定O(√n)
def is_prime(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            return False
        i += 1
    return n != 1    # 1の場合は例外

実行結果

False

約数の列挙（O(√n)）

# 約数の列挙O(√n)
def divisor(n):
    res = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            res.append(i)
            if i != n // i:
                res.append(n // i)
        i += 1
    return res

実行結果

[1, 295927, 541, 547]

素因数分解（O(√n)）

# 素因数分解O(√n)
def prime_factor(n):
    res = {}
    i = 2
    while i * i <= n:
        while n % i == 0:
            if not i in res:
                res[i] = 0
            res[i] += 1
            n //= i
        i += 1
    if n != 1:
        res[n] = 1
    return res

実行結果

{541: 1, 547: 1}