Python - 関数(素数)

初めてのPython 第3版
Mark Lutz (著)

開発環境

• OS X Lion - Apple(OS)
• BBEdit - Bare Bones Software, Inc.(Text Editor)
• プログラミング言語: Python

『初めてのPython 第3版』(Mark Lutz 著、夏目 大 訳、オライリー・ジャパン、2009年、ISBN978-4-87311-393-7) のIV部(関数)のまとめ演習8.(素数)を解いてみる。

その他参考書籍

• Pythonチュートリアル 第2版
• Python クックブック 第2版

8.(素数)

コード(BBEdit)

sample.py

#!/usr/bin/env python3.3
#-*- coding: utf-8 -*-

def isPrime(y):
    x = y // 2
    while x > 1:
        if y % x == 0:
            return "{0} has factor {1}".format(y, x)
        x -= 1
    return "{0} is prime".format(y)

for x in [13, 13.0, 15, 15.0]:
    print(isPrime(x))

# while loop よりfor loopの方が速い
def isPrime1(y):
    x = int(y // 2)
    for n in range(x, 1, -1):
        if y % n == 0:
            return "{0} has factor {1}".format(y, n)
    return "{0} is prime".format(y)

for x in [13, 13.0, 15, 15.0]:
    print(isPrime1(x))

# 実際に速いかどうか速度を比較
n = 10 ** 4
import time
start = time.clock()
for x in range(n):
    isPrime(x)
print(time.clock() - start)
start = time.clock()
for x in range(n):
    isPrime1(x)
print(time.clock() - start)

入出力結果(Terminal)

$ ./sample.py
13 is prime
13.0 is prime
15 has factor 5
15.0 has factor 5.0
13 is prime
13.0 is prime
15 has factor 5
15.0 has factor 5
2.217495
1.6200230000000002
$

ちなみにJavaScriptの場合。

コード(BBEdit)

var f = function ( y ) {
    var x = Math.floor(y / 2);
    while ( x > 1 ) {
        if ( y % x === 0 ) {
            return y + " has factor " + x;
        }
        x -= 1;
    }
    return y + " is prime";
},
    g = function ( y ) {
        var x = Math.floor( y / 2 ),
            i;
        for ( ; x > 1; x -= 1) {
            if( y % x === 0 ){
                return y + " has factor " + x;
            }
        }
        return y + " is prime";
    },
    nums = [13, 13.0, 15, 15.0],
    result = "",
    i, max, start, n;
for (i = 0, max = nums.length; i < max; i += 1) {
    result += f(nums[i]) + "\n";
}
for (i = 0, max = nums.length; i < max; i += 1) {
    result += g(nums[i]) + "\n";
}

// pythonではwhile loopよりfor loopの方が速かったけど、
// JavaScriptではどうかを計測して確認
n = Math.pow(10, 4);
start = new Date().getTime();
for (i = 0, max = n; i < max; i += 1) {
    f( i );
}
result += (new Date().getTime() - start) / 1000 + "\n";
start = new Date().getTime();
for (i = 0, max = n; i < max; i += 1) {
    g( i );
}
result += (new Date().getTime() - start) / 1000 + "\n";
$('#pre0').text(result);

JavaScriptだと、少なくとも今回の場合はwhile loopもfor loopもそんなに変わりないみたい。(FirefoxとSafariで確認)