第20回【Python】素数の個数、log2

2023年2月21日

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

はじめに

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

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

うわぁお。20 回ですよ。誰か褒めて。いやいや、自分自身のために勝手にやってることだから、別に褒められることではないって。一人で浮かれてみました。いたって本気で真面目です。

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

素数の個数

LeoSaki（旦那）は素数が大好き。いろいろな求め方がありますが、とりあえずは一番単純で分かりやすい方法にしよう。

Python

N = int(input())
cnt = 0
for i in range(2,N+1):
    for j in range(2,int(i**0.5)+1):
        if i % j == 0:
            break
    else:
        cnt += 1
print(cnt)

2 ～ N までの数字（i）を、2 ～ √i までの数字で割って、どの数字でも割り切ることができなければ、それは素数。（2 ～ N までの数字を 2 ～ N まで割ってもいいけれど、数が大きくなればなるほど時間がかかる）

for 文で利用できる else 文も覚えておくといいかもしれない。LeoSaki（旦那）も、for – else 文を知ったのは最近で、それまではよくあるフラグを利用した方法で書いていた。知っているだけで、こんなに簡潔に書けるなんて素晴らしい！

では、VBA でも書いてみる。

VBA

N = Cells(1, 1)
cnt = 0
For i = 2 To N
    flg = True
    For j = 2 To Int(Sqr(i))
        If i Mod j = 0 Then
            flg = False
            Exit For
        End If
    Next
    If flg Then cnt = cnt + 1
Next
Debug.Print cnt

フラグです。for – else 文がないので、フラグで管理する方法しか思いつかない。

log2

この問題を読んですぐに理解できる人ってどのくらいいるんだろう。単純に、N の階乗を 2 で何回割ることができるか、ってことなんだと思う。ただ、膨大な数になりすぎるので、工夫が必要、ってことかな？

Python

N = int(input())
cnt = 0
for i in range(1,N+1):
    tmp = i
    while tmp % 2 == 0:
        cnt += 1
        tmp //= 2
print(cnt)

正直に言おう。最初は、N の階乗の求め方を考えていた。しかし、そんな大きな数を処理する必要があるか悩んで、若かりし頃の学びを思い出した。先に階乗求める必要ないやん！

同じことが VBA でもできるかな？

VBA

N = Cells(1, 1)
cnt = 0
For i = 1 To N
    tmp = i
    Do While tmp Mod 2 = 0
        cnt = cnt + 1
        tmp = tmp / 2
    Loop
Next
Debug.Print cnt

できたできた。速度も申し分なし。まだ・・・頑張れる。

最後に

始めた当初は、こんな内容で 20 回も続けるとは思っていなかった。もっと手応えのある難しい問題にさっさと手を付けて、こんな序盤のループ（for 文や while 文）は飛ばそうと思っていた。正直なところ。

しかし、継続は力なり。すらすらと書くことができてくると楽しいものだ。頭の中の整理も早くなったと思う。

あくまでも LeoSaki（旦那）は Python の初心者、というところを忘れないようにしたい。

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