problem3

続きで、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もそうだった。
  • 無限リストがあれば、素数ジェネレータ作れる? 動いたけど合ってるのかな。
  • デフォルト引数を簡単に書けて嬉しい。

Leave a Comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.