#約数を列挙するプログラム
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
#最後に
もっといい方法があれば知りたいです