続きで、Project Eulerの問題をpythonで

数学をWikipediaで調べ、pythonをgoogleで調べながら解いたので、骨の折れる問題でした。(特に数学的な意味で)

#! /usr/bin/python
# -*- coding: cp932 -*-
'''
13195 の素因数は 5、7、13、29 である。
600851475143 の素因数のうち最大のものを求めよ。
'''
def infListFrom(n):
"無限リストを返す。"
while 1:
yield n
n += 1
def some(fun, list):
"用意されてるかもしれないけど、自作"
for i in list:
if fun(i):
return True
return False
def genPrimeNumber():
"素数ジェネレータ"
infList = infListFrom(2)
for i in infList:
if not some(lambda(x): i % x == 0, range(i / 2, 1, -1)):
yield i
raise Exception, 'it never reach here.'
def getPrimeFactors(n, acc = []):
"引数 n を素因数分解する。"
if n == 1:
return acc
for i in genPrimeNumber():
if n % i == 0:
acc.append(i);
return getPrimeFactors(n / i, acc)
raise Exception, 'failed to get prime factors.'
answer = max(getPrimeFactors(600851475143))
print answer

思ったことなど

• 素因数分解ってこと？素因数分解って何だっけ？
• 素数ってどうやって求めるんだっけ？エラトステネスの篩？結局もっと原始的に実装した。
• pythonらしい命名規則とはどっちなんだろう？ primeNumbers or prime_numbers
• some関数とかany関数は無いのか？
• someを作った。でも実際、filterで十分だった。
• 変数で受けとった関数を、実行するの超楽(funcallしないでいい)。なんか、おもちゃで遊んでる感覚。javascriptもそうだった。
• 無限リストがあれば、素数ジェネレータ作れる？ 動いたけど合ってるのかな。
• デフォルト引数を簡単に書けて嬉しい。