整数問題用のライブラリ

競技プログラミングでは、数学の整数分野の問題がよく出題されます。
この記事では、書くことが多い処理をpythonで関数化したコードを紹介します。
詳しくは、下記のGitHubの方も参考にしてみて下さい。

github.com

最大公約数, 最小公倍数

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

2つの整数の最大公約数、最小公倍数を返します。

約数

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    table.sort()
    return table

入力された整数の約数の一覧をリストで返します。

素因数分解

#nを素因数分解したリストを返す
def prime_factor(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

整数を素因数分解して、要素をリストで返します。

素数判定

#引数nが素数かどうかを判定
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1

入力された整数が素数であるか判定

エラトステネスの篩

#nまでの素数を列挙(エストラステネスの篩)
def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i

    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table

入力された整数までの素数をリストで返します。 また、それぞれが素数であるかを判定したリストも返します。

順列、組み合わせ

import math
def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)

順列、組み合わせの数を返します。