Python でエラトステネスのふるいを書いてみた

エラトステネスのふるい（sieve of Eratosthenes）は、
ある数が素数であるか判別するためのアルゴリズムだ。

関数 sieve_of_Eratosthenes_v1 は、
「調べる数」を、「調べる数/2」以下の全ての整数で割って、
割りきれなければ素数とする。
10000までの素数を調べた時の実行時間（10回の平均）：0.962354秒

関数 sieve_of_Eratosthenes_v2 は、
「調べる数」を、「素数」で割って、
割りきれなければ素数とする。
10000までの素数を調べた時の実行時間（10回の平均）：0.098287秒

v2 は v1 より10倍速い。いいね！　←自己満足

get_prime_numbers.py

def sieve_of_Eratosthenes_v1(p_terminal_number) :
    """
    The purpse of this function is get prime numbers
    using algorithm 'The sieve of Eratosthenes'.
    broken number: from '2' to terminal number. 
    divided number: from '2' to 'broken number / 2'. 
    When broken number can't be divided by divided number,
    broken number is prime number.
    """

    broken_number = range(p_terminal_number + 1)
    prime_numbers = [ ]
    for broken in broken_number[ 2: ] :
        last_check = broken / 2
        divided_number = range(last_check+1)
        for divided in divided_number[ 2: ]:
            if broken % divided == 0 :
                break
            else :
                pass
        else:
            prime_numbers.append(broken)
    return prime_numbers


def sieve_of_Eratosthenes_v2(p_terminal_number) :
    """
    The purpse of this function is get prime numbers
    using algorithm 'The sieve of Eratosthenes'.
    broken number: from '3' to terminal number. 
    divided number: prime numbers.
    When broken number can't be divided by prime numbers,
    broken number is prime number.
    """

    broken_number = range(p_terminal_number + 1)
#  set initial prime number
    prime_numbers = [2]
    for broken in broken_number[ 3: ] :
        for prime in prime_numbers :
            if broken % prime == 0 :
                break
            else :
                pass
        else :
            prime_numbers.append(broken)
    return prime_numbers

ちなみに実行時間はこんな感じで調べた。
measure.py

def measure_run_time(p_function_name, p_arg01) :
    import time

    time_history = [ ]
# call fucntion 10 times
    loop_count = 10
    while loop_count:
        start_time = time.clock( )
 # call function of parameter function name
        p_function_name(p_arg01)
        end_time = time.clock( )
        run_time = end_time - start_time
        time_history.append(run_time)
        loop_count = loop_count - 1
    time_history.sort( )
    for run_time in time_history:
        print 'run time   %f second' % (run_time)

    total = 0
 # get average without best result and worst result
    for run_time in time_history[1:9]:
        total = total + run_time
    else:
        average = total / 8
        print '%f' % average

if __name__ == '__main__' :
    import sys
    import get_prime_numbers
    measure_run_time(get_prime_numbers.sieve_of_Eratosthenes_v1, 10000)
    measure_run_time(get_prime_numbers.sieve_of_Eratosthenes_v2, 10000)