素数を書き出すプログラムの良しあしを判断してほしい

実現したいこと

素数を書き出すプログラムの良しあしを判断してほしい

前提

現在Pythonにて、簡単な素数判定プログラムを作成しました。

以下のコードについて、わかりにくい点や修正すべき点、バグが入り込む余地やさらに良いプログラムがあれば、ご教示いただきたいです。
現在コーディングテストに向けての学習を行っておりますので、テストでの合格基準をもとに判断していただけますと非常にありがたいです。

該当のソースコード

Python

1for num in range(2, 100):2 i = 23 x = num 4 while i < x:5 if num % i == 0:6 break7 else:8 x = num // i 9 i += 110 else:11 print(num)

まず、このコードを説明いたします。

素数というのは、「一とその数自身との外には約数がない正の整数。」ということですので、例えば100が素数かを判定するために、2から99までの数字で割り切れるかを見ることで、素数かどうかを判定することもできます。
しかしながら、それでは素数かを判定する数字が大きくなればなるだけ、プログラムの実行が重くなってしまいます。

そこで上記のプログラムでは、約数があるかをもとに考えました。

例えば97が素数かを判断するためにまず2で割ると
97÷2=48 あまり1
となるので、48以上の数字に約数がないことがわかります。また、
97÷3=32 あまり1
なので、32以上の数字にも約数がないことがわかります。
このように、2, 3, 4…と小さな数字で順に割っていくことで素数かを判定すると同時に、判定しなければならない数値の範囲を狭めています。

上記のコードのfor文にて、num = 17の時を考えますと、

Python

1i = 22x = num #x = 173while i < x: #while文1回目:2 < 17が成り立つ4 if num % i == 0: # 成り立たない5 break6 else:7 x = num // i # xに17 // 2(=8)を代入8 i += 1 #iに3を代入9else:10 print(num)

次、i = 3の時

Python

1while i < x: #while文2回目:3 < 8が成り立つ2 if num % i == 0: # 成り立たない3 break4 else:5 x = num // i # xに17 // 3(=5)を代入6 i += 1 #iに4を代入7else:8 print(num)

次、i = 4の時

Python

1while i < x: #while文3回目:4 < 5が成り立つ2 if num % i == 0: # 成り立たない3 break4 else:5 x = num // i # xに17 // 4(=4)を代入6 i += 1 #iに5を代入7else:8 print(num)

次、i = 5の時

Python

1while i < x: #while文4回目:5 < 4なので成り立たない2 if num % i == 0: # 実行されない3 break4 else:# 実行されない5 x = num // i 6 i += 1 7else:8 print(num) #num(=17)が出力される

上記のコードについて、わかりにくい点や修正すべき点、バグが入り込む余地等があれば、ご教示いただきたいです。

コメントを投稿

0 コメント