第14回【Python】約数の個数、約数の列挙

2023年1月19日

現在取り組んでいるのは、paiza ラーニング問題集「ループメニュー 2」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 14 回目です。

今回で「ループメニュー 2」が終了します。繰り返し、似たようなコードを書き続けているので、相当に身についてきているような気がしています。間違えやすいところとか、よーく理解できてきた！

それでは、今日も頑張ってみようと思います。

約数の個数

「約数とは、N を割り切る整数のことを指します」って丁寧だな！ こないだ、階乗の解のゼロの個数を調べるために素因数分解を繰り返した LeoSaki（旦那）に死角なし。

Python

N = int(input())
cnt = 0
for i in range(1,N+1):
    if N % i == 0:
        cnt += 1
print(cnt)

計算量を減らすために、組になる数を取得すればいいんじゃなかろうか、って思ってみた。

Python

import math
N = int(input())
n = math.ceil(N ** 0.5)
cnt = 0
if n == N/n:
    cnt += 1
for i in range(1,n):
    if N % i == 0:
        cnt += 2
print(cnt)

うーん、なんか逆に複雑になっているような気がしなくもない。平方根を切り上げで取得して、整数となる平方根を持つ N の場合は、あらかじめ cnt に 1 を追加（100 の場合、10 が平方根となるので、cnt += 1）。あとは、平方根まで余りの出ない数を探索。

物凄く大きな数を調査するのならば、早そうではあるけれど。どうなんでしょう。（1000 の 2 乗なんかで計算してみると、確かに速いことを確認しました！ さらに桁数を増やすと、明らかな差が発生していました）

VBA でもやることは同じ。

VBA

N = Cells(1, 1)
cnt = 0
For i = 1 To N
    If N Mod i = 0 Then cnt = cnt + 1
Next
Debug.Print cnt

ついでに、平方根を利用した計算量減少のコードも試してみる。

VBA

N = Cells(1, 1)
sqrn = Application.WorksheetFunction.RoundUp(Sqr(N), 0)
cnt = 0
If sqrn = N / sqrn Then cnt = cnt + 1
For i = 1 To sqrn - 1
    If N Mod i = 0 Then cnt = cnt + 2
Next
Debug.Print cnt

おもいっきり桁数を増やしてみたら、前者ではしばらく固まり、後者ではあっさり計算完了した。for 文の範囲指定の違いを意識して、きちんと -1 することを忘れちゃいけない。

約数の列挙

大きい数値にするとどうなっちゃうんだろう、とかドキドキしますね。ただ、ちゃんと条件を読むと、N の値の範囲は 1 <= N <= 1000 なんだそうです。いや、そんなの知らない。試してみる！

しかし、まずは正攻法から。

Python

N = int(input())
for i in range(1,N+1):
    if N % i == 0:
        print(i)

問題に「小さい方から順に」とある。ちょっと工夫が必要みたい。

import math
N = int(input())
n = math.ceil(N ** 0.5)
L = []
if n == N/n:
    L.append(n)
for i in range(1,n):
    if N % i == 0:
        L.append(i)
        L.append(N//i)
L.sort()
print(*L,sep="\n")

少しは勉強している効果が出たかしら？ リストに入れて、リストを並び替えて、出力する。

桁数をバカみたいに増やしてみたら、前者はタイムアウト、後者はきちんと出力された。素晴らしい！

同じことを VBA でもやってみちゃる。

VBA

N = Cells(1, 1)
For i = 1 To N
    If N Mod i = 0 Then Debug.Print i
Next

まぁ、そこそこの桁数までは簡単に出力可能だ。しかし、桁数が増えていくと、徐々に遅くなっていく。

で、平方根を利用したコードを作ってみた。うーん、これで早くなってるのか？

VBA

Dim L As Variant
N = Cells(1, 1)
sqrn = Application.WorksheetFunction.RoundUp(Sqr(N), 0)
L = Array()
cnt = 0
If sqrn = N / sqrn Then
    ReDim Preserve L(cnt)
    L(cnt) = sqrn
    cnt = cnt + 1
End If
For i = 1 To sqrn - 1
    If N Mod i = 0 Then
        ReDim Preserve L(cnt)
        L(cnt) = i
        cnt = cnt + 1
        ReDim Preserve L(cnt)
        L(cnt) = N / i
        cnt = cnt + 1
    End If
Next
L = Application.WorksheetFunction.Sort(L, 1, 1, True)
For Each Item In L
    Debug.Print Item
Next

1000 の 2 乗の後ろに 100 を追加して 10億100 で試してみたら、明らかな差が出ました。素晴らしい！
ただし、VBA で sort 関数は office365 でしか使用できないらしい。もし、office365 以外で試すのならば、昔ながらの VBA での sort を作る必要があるみたい。

最後に

ちょっとお遊びを入れながら、「ループメニュー 2」を完走しました。その感想は、とても身に着いた実感がある！ です。for 文や while 文を繰り返し使うことで、ありがちなミスに引っかからない「癖」がついたように思います。

最後の平方根を利用した約数の列挙は、なんかとても面白かった。思いついたのは、なんかの機会に Pythonでは「**0.5」で平方根を求められるってことを偶然知ったから。やっぱり、学び続けることは大事だ！

まぁ、最後、VBA で書いたコードは長くなってしまって、Python との差を思い知らされる結果になってしまったけれど。

次は、「二重ループメニュー」に挑戦してみたいと思います！

引き続き、お付き合いよろしくお願いいたします！