20 October, 2008

[Project Euler] Problem 21

Problem 21

素数リストとかは過去の問題のを使い回し。

object P021 {
val initPrimes:List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101)
def primes(init:List[Int]):List[Int] = {
def min(a:Int, b:Int) = if (a<b) a else b
def sq(a:Int) = a*a
init ::: List.range(init.last+1, min(100000,sq(init.last))).filter{x => init.forall{x%_!=0}}
}
val primeList:List[Int] = primes(primes(initPrimes))
def factors(n:Int):List[Tuple2[Int,Int]] = {
def g(n:Int, p:Int, c:Int):Tuple2[Int,Int] = if (n%p==0) g(n/p, p, c+1) else Tuple2(n,c)
def f(n:Int, ps:List[Int], ts:List[Tuple2[Int,Int]]):List[Tuple2[Int,Int]] = (n,ps) match {
case (1,_) => ts
case (_,Nil) => error("n="+n)
case (_, a::as) if n%a==0 => {
val z = g(n,a,0)
f(z._1, as, Tuple2(a,z._2)::ts)
}
case (_, a::as) => f(n, as, ts)
}
f(n, primeList, Nil)
}
def sumDiv(ts:List[Tuple2[Int,Int]]):Int = {
def pow(a:Int, b:Int):Int = b match {
case 0 => 1
case _ => pow(a,b-1)*a
}
def f(t:Tuple2[Int,Int]):Int = {
List.range(0, t._2 +1).map{pow(t._1, _)}.foldLeft(0)(_+_)
}
ts.map(f).foldLeft(1)(_*_)
}
def sumDivisors(n:Int):Int = sumDiv(factors(n))-n
def main(args:Array[String]) {
println(sumDivisors(220))
println(sumDivisors(284))
val l = List.range(2,10000).filter{a => {
val b=sumDivisors(a)
val c=sumDivisors(b)
val r=(a!=b)&&(a==c)
if (r) println(a+"<->"+b)
r
}}
println(l)
println(l.foldLeft(0)(_+_))
}
}

---
 ここまでProject Eulerを解いてきて思ったのだが、組み込みライブラリとか言語仕様で、

  • アノテーションを付けるだけで関数の値をメモ化してくれる。
  • とりあえず1,000,000以下の素数は予め計算されている。
  • 内部でIntの計算が桁溢れしたら勝手にLong -> BigInt と桁を増やしてくれるような数値型。
  • 素因数分解も組み込み関数で用意されている。
とかだと、かなり楽が出来るのになぁ...。

No comments: