[python]約数を列挙するプログラム

約数を列挙するプログラム

Pythonを利用して自然数の約数を取得する
プログラムの何通りか

約数とは
数学において、整数 N の約数（やくすう、英: divisor）とは、N を割り切る整数またはそれらの集合のことである。
割り切るかどうかということにおいて、符号は本質的な問題ではないため、N を正の整数（自然数）に、約数は正の数に限定して考えることも多い。
自然数や整数の範囲でなく文字式や抽象代数学における整域などで「約数」と同様の意味を用いる場合は、「因数」（いんすう）、「因子」（いんし、英: factor）が使われることが多い。
整数 a が整数 N の約数であることを、記号 | を用いて a | N と表す。

listの内包表記

一番簡潔にかける書き方

list.py

num = 30
answer = [i for i in range(1, num+1) if num % i ==0]
print(answer)

#結果：[1, 2, 3, 5, 6, 10, 15, 30]

While

約数を大きい順に出力

while.py

n = 30
x = n

while n > 0:
    if x % n ==0:
        print(n)
    n -= 1

#結果：30, 15, 10, 6, 5, 3, 2, 1

約数を小さい順に出力

while.py

n = 1
x = 30

while n <= 30:
    if x % n ==0:
        print(n)
    n  +=  1

#結果：1, 2, 3, 5, 6, 10, 15, 30

関数

nに数字を与えることで結果を返す

while.py

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table =sorted(list(set(table)))
    return table
#結果：[1, 2, 3, 4, 6, 12, 37, 74, 111, 148, 222, 444]

関数⑵

@taC_hさんより

・pythonはwhileよりforのほうが速い
・loop毎のi*i <= nを外に出したい
・sortはO(nlogn),コピーはO(n)

for.py

def divisor(n):
    sq = n**0.5
    border = int(sq)
    table = []
    bigs = []
    for small in range(1, border+1):
        if n%small == 0:
            table.append(small)
            big = n//small
            bigs.append(big)
    if border == sq:#nが平方数
        bigs.pop()
    table += reversed(bigs)
    return table

最後に

もっといい方法があれば知りたいです