Problem 3
13195 の素因数は 5、7、13、29 である。
600851475143 の素因数のうち最大のものを求めよ。
Solution
あまりうまい書き方が思い浮かばなかったので手続き型で。
といってもコードはここから借りてきただけだけ。
mod ?= (x, n) -> x % n == 0 Array::max = -> Math.max.apply Math, this prime_factors = (x) -> result = [] max = Math.floor(Math.sqrt(x)) n = 2 while n <= max if mod? x, n x /= n result.push(n) n++ result num = 600851475143 console.log prime_factors(num).max()
プロトタイプ拡張も簡潔にかけてCoffeeScriptいいかもしれない。
ときに
このコードの実行時間は、
start = Date.now() console.log prime_factors(num).max() console.log "#{Date.now() - start} ms" #=> 61 ms
だった。これはprime_factorsを次のように書き換えることで改善できる。
prime_factors = (x) -> result = [] max = Math.floor(Math.sqrt(x)) n = 2 if mod? x, n result.push(n) x /= n n++ while n <= max if mod? x, n x /= n result.push(n) n += 2 result #...中略... start = Date.now() console.log prime_factors(num).max() console.log "#{Date.now() - start} ms" #=> 30 ms
あらかじめ2の倍数の処理を省いておくことで実行時間は半分程になる。
もっと速く！
3と5で割り切れる場合も前処理しておくと更に速くなる。でもこれは汚いコードだ！
prime_factors = (x) -> result = [] max = Math.floor(Math.sqrt(x)) ns = [2, 3, 5] for n in ns if mod? x, n result.push(n) x /= n n = 6 while n <= max if mod? x, n-1 x /= n - 1 result.push(n) else if mod? x, n+1 x /= n + 1 result.push(n) n += 6 result #...中略... start = Date.now() console.log prime_factors(num).max() console.log "#{Date.now() - start} ms" #=> 20 ms
リンク先に
Problem #10までの解が載っているのだけど、もっと上手い記述がないか考える。
順路：CoffeeScriptでProject Euler #4
逆路：CoffeeScriptでProject Euler #2
