OSANAI.ORG

Python で素数を数え上げる

Project Euler で素数（prime number）を求める必要があったので考えて何とかやってみました。 ググってしまえばすぐに先人の素敵なプログラムを参照できるところですがそれだと自分の勉強にならないので何も見ずに考えたところ、以下のようになりました。

#!/usr/bin/env python
#-*- coding: utf-8; -*-

import sys

argvs = sys.argv
arg = int(argvs[1])

def old_primes(arg):
    counter = 0
    primes = [2]
    def is_prime(arg):
        nonlocal counter
        counter += 1
        if arg % 2 == 0:
            return False
        else:
            for i in range(3, arg, 2):
                counter += 1
                if arg % i == 0:
                    return False
            return True
    for n in range(3, arg):
        if is_prime(n):
            primes.append(n)
        else:
            pass
    print(primes)
    print('len:', len(primes))
    print('counter:', counter)


def main():
    old_primes(arg)


if __name__ == '__main__':
    main()

実行結果はこうなります。

$ python prime_number.py 1000
[2, 3, 5, 7, 11, 13,
（中略）
 983, 991, 997]
len: 168
counter: 39675

そのあとでこちらのエントリでよりスマートなアルゴリズムを知りました。ある数の平方根より小さい素数で割り切れなければその数は素数である、という判定ができるのですね。

また、↑のスクリプトは判定アプローチ（2 で割って、奇数で割っていく）は自分だけで考えたところですが、変数 counter で計算回数を数えるというのは上記エントリを見てから組み込みました。

こちらのエントリではもう少し複雑っぽいスクリプトが紹介されていました。ifilter などを調べる必要がありまだちゃんと読めていないのですが、こちらも勉強になります。