素数を求めるプログラムを作りたい

Question

前提・実現したいこと

素数を求めるプログラムを書いたのですが

発生している問題・エラーメッセージ

実行した結果、なぜか４が入ってしまいました。また、１００までとしたはずが１０１まで出てしまいました。
なぜなのか、またどうしたら良いか、ご教示願えませんでしょうか？

また、勉強中なので他にこのコードに対する意見やアドバイスがあれば書いていただければ嬉しいです。
よろしくお願いいたします。

該当のソースコード

i = 3
imax = 2
sosu=[2]
while i <= 100 :                    #iを100 まで繰り返す
    imax=2
    while i/2 > imax  :             #2からiの半分までの数(imax)で割った余りを調べる
       if i%imax == 0 :             #余り０なら次のi
          i += 1
          imax=2
       else :                       #そうでないなら次のimax
          imax += 1
    sosu.append(i)  
    i += 1

print(sosu)

【結果】
[2, 3, 4, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

pp.py

import math

def is_prime(n, primes):
    # この時点でわかっている素数 で sqet(n) 以下の数を試していく
    max_p = int(math.sqrt(n))
    for p in primes:
        if p > max_p:
            break
        if n % p == 0:
            return False
    return True

MAX = 100
# 3, 5, 7 ...　のようにして MAX 以下の奇数だけを試していく
primes = [2]
for p in range(3, MAX + 1, 2):
    if is_prime(p, primes):
        primes.append(p)

print(primes)

実行例：

Comments

[masimarow]

なるほど！勉強になりました！ありがとうございます！

Answer 2

なぜか４が入ってしまいました。

i=4の時にどういう処理をされるかを読めば、素数と判定されることが分かります。
while 4/2 > 2:の条件が偽なので、一度もwhile内を実行せずに、sosu.append(4)が実行されます。

１００までとしたはずが１０１まで出てしまいました。

i <= 100を判定した後でi+=1しているからですね。

またどうしたら良いか、

場当たり的にコードを書かず、トップダウンで設計するといいです。

sosu = [2]
for i in range(3,101):
    if is_sosu(i):
        sosu.append(i)

のようにして、True/Falseを返すようにis_sosu関数を作ってください。
range(3,101,2)とすれば最初から偶数を除外できます。

Comments

[masimarow]

迅速な回答ありがとうございました。