読者です 読者をやめる 読者になる 読者になる

Pythonで関数型言語っぽくエラトステネスの篩

最近関数型言語始めようと「すごいH本」買ってHaskellはじめました。が、いかんせん文法なれない...そこで概念を理解しているというか多少は慣れてるPythonでいろいろ実装してみてます。その第一弾。エラトステネスの篩。なぜこれか?実はサークルのC++講座の課題で出したので僕はこれを関数が多っぽく書こうと思い。
以下のようなコードになりました。

def getPrimeList(m):

	def PrimeList_imp(PrimeList,n):
		if (len(PrimeList)==(n)):
			return PrimeList
		return PrimeList_imp(filter(lambda x: ((x%PrimeList[n]!=0) or (x==PrimeList[n])), PrimeList), n+1)

	return PrimeList_imp(range(m)[2:], 0)

print getPrimeList(20)

とりあえず、getPrimeListでmまでの素数列を取得します。実装はPrimeList_impでしています。基本的にはフィルタでその数で割り切れるものを取り除く(正確には割り切れないものを残す)というやり方でしています。ただ、これだと自分自身を割ってしまうのでそこはそれを無視するようにしています。あとは再帰的に呼び出してあげればおk。終了条件としてはリストの要素数とnが一致したらということにしてあります。ここら辺で無駄な部分があるのでもっとスマートに出来そう...