P37 (**) Calculate Euler's totient function phi(m) (improved).
前回トーシェント関数を愚直にひとつひとつ互いに素かどうかを調べていたけど、素因数分解を利用して解くことができるらしい。
p36.cljで作った
my-prime-factors-multを使って解いてみる。my-prime-factors-mult、ほんの少しだけ変えていて、loop/recurの中でmをインクリメントしながら再帰呼び出しするのではなく、最初に
'(2 3 5 7 ...)と2と奇数のリストを作っている。こちらのほうが再帰のときに2だったら+1,それ以外だったら+2とせずに済む(どうせ最初の一回以外全て+2するわけだし)。
あと、問題文の公式が(多分)間違っていて少し戸惑った。
- 誤
-
phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...
- 正
-
phi(m) = (p1 - 1) * p1 ** (m1 - 1) * (p2 - 1) * p2 ** (m2 - 1) * (p3 - 1) * p3 ** (m3 - 1) * ...
P38 (*) Compare the two methods of calculating Euler's totient function.
ちょっと変わり種の問題(?)、p34.cljとp37.cljのパフォーマンスを比較する。timeマクロを使って、こんな感じか。新しく書いたのは
my-measure-phi関数のみで、その他はp34.cljとp37.cljをそのまま使っている。結果としては、素因数分解を用いたバージョンのほうが物凄く性能が良いという事のようだ。
user=> (my-measure-phi 10090) "Elapsed time: 16.896419 msecs" "Elapsed time: 0.114895 msecs" nil user=> (my-measure-phi 10090) "Elapsed time: 13.035887 msecs" "Elapsed time: 0.234636 msecs" nil user=> (my-measure-phi 10090) "Elapsed time: 11.809389 msecs" "Elapsed time: 0.197859 msecs" nil user=> (my-measure-phi 10090) "Elapsed time: 11.926565 msecs" "Elapsed time: 1.650726 msecs" nil user=> (my-measure-phi 10090) "Elapsed time: 1.954641 msecs" "Elapsed time: 0.057875 msecs" nil
P39 (*) A list of prime numbers.
これもHaskell版のZaneli.Euler.primesをほぼまるっとClojureに書き換えた。下限と上限を渡してその範囲の素数を返す関数が必要なので、
my-primesで2から上限までの素数を作り、my-primes-rangeでそこから下限以上のみの素数を作っている。(前者は降順、後者は昇順なのが統一感が無くちょっといびつかもしれない…)