素数を求める (ver.5)

明解Ｃ言語 入門編 > 5. 配列 >

素数を求める (ver.5)

Python

# coding: Shift_JIS

prime    = [] # range(15)
prime.append(2)
prime.append(3)
ptr      = 2

counter = 0
no      = 5
while (no <= 30):
    j = 0
    i = 1
    while True:
        counter += 1
        if (prime[i] * prime[i] > no):
            break 

        counter += 1
        if (no % prime[i] == 0):
            j = 1
            break # 割り切れるので、素数ではない
        i += 1

    if j == 0:
        prime.append(no) # 最後まで割り切れなかったので、素数
        ptr += 1

    no += 2

for p in prime:
    print p

print "計算を行った回数：%d" % counter

実行結果

N:\>python lesson_05_042.py

2

3

5

7

11

13

17

19

23

29

計算を行った回数：34