ScalaでProject Euler（77）

Problem 47

順番に素因数分解を生成しても遅くないのですが、それでは面白くないので別の方法を考えましょう。4つの素数から成る数を昇順に生成すればよいのです。これは、約数の個数がある数より大きい自然数を昇順に列挙する（1）とほとんど同じです。初期の指数の並びが[1, 1, 1, 1]であるのと、項数が増えないことくらいです。
しかし、このくらいの数の大きさだと速度はほとんど変わらないです。

import scala.collection.mutable.ArrayBuffer
import scala.collection.mutable.PriorityQueue
import scala.collection.mutable.Set
import Math.sqrt
import scala.testing.Benchmark

object Prime {
    val primes = new ArrayBuffer[Int]
    primes += 2
    
    def apply(k :Int) =
        if(k < primes.size)
            primes(k)
        else {
            for(n <- Stream.from(primes(primes.size-1) + 1).
                    takeWhile(n => k >= primes.size) if is_prime(n))
                primes += n
            primes(primes.size-1)
        }
    
    def is_prime(n :Int) =
        primes.takeWhile(p => p * p <= n).forall(n % _ != 0)
}

def pow(n :Int, e :Int) =
    (1 to e).foldLeft(1L)((x, y) => x * n)

def value(es :List[Int]) =
    es.zip(0 to (es.size - 1)).foldLeft(1L)(
                (x, y) => x * pow(Prime(y._2), y._1))

def num_divs(es :List[Int]) =
    es.foldLeft(1)((x, y) => x * (y + 1))

class gen_combinations(L :Int) extends Iterator[(Long,List[Int])] {
    val o = Ordering[Long].on[(Long,List[Int])](-_._1)
    val pq = new PriorityQueue[(Long,List[Int])]()(o)
    val init_es = List.range(0, L).map(k => 1)
    pq.enqueue((value(init_es), init_es))
    
    def hasNext() = true
    
    def next() = {
        val (v0, es0) = pq.dequeue
        
        val es1 = (es0.head + 1) :: es0.tail
        pq.enqueue((value(es1), es1))
        next_combination(Some(es0)).foreach(es => pq.enqueue((value(es), es)))
        
        println (v0, es0)
        (v0, es0)
    }
    
    def next_combination(es :Option[List[Int]]) :Option[List[Int]] = es match {
        case Some(e1 :: e2 :: tail) if e1 == e2 + 1 => Some(e1 :: e1 :: tail)
        case Some(e1 :: e2 :: tail) if e1 == e2 =>
            next_combination(Some(e2 :: tail)).map(e2 :: _)
        case _ => None
    }
}

def is_descending(es :List[Int]) =
    es.zip(es.tail).forall(x => x._1 >= x._2)

class gen_permutations(L :Int) extends Iterator[(Long,List[Int])] {
    val o = Ordering[Long].on[(Long,List[Int])](-_._1)
    val pq = new PriorityQueue[(Long,List[Int])]()(o)
    val g = (new gen_combinations(L))
    val set_used = Set[Long]()
    
    put(g.next)
    
    def hasNext() = true
    
    def next() = {
        val (v0, es0) = pq.dequeue
        
        val ess = next_permutation(es0).
                    filter(es => !set_used.contains(value(es)))
        for(es <- ess) put((value(es), es))
        
        if(is_descending(es0))
            pq.enqueue(g.next)
        
        (v0, es0)
    }
    
    private def put(x :(Long,List[Int])) = {
        pq.enqueue(x)
        set_used += x._1
    }
    
    def next_permutation(es :List[Int]) :List[List[Int]] = es match {
        case (e1 :: e2 :: tail) if e1 > e2 =>
                (e2 :: e1 :: tail) :: next_permutation(e2 :: tail).map(e1 :: _)
        case (e1 :: e2 :: tail) => next_permutation(e2 :: tail).map(e1 :: _)
        case _ => Nil
    }
}

class gen_numbers(L :Int) extends Iterator[Long] {
    val o = Ordering[Long].on[(Long,List[Int])](-_._1)
    val pq = new PriorityQueue[(Long,List[Int])]()(o)
    val g = new gen_permutations(L)
    
    pq.enqueue(g.next)
    
    def hasNext() = true
    
    def next() = {
        val (v0, es0) = pq.dequeue
        
        val rev_es0 = es0.reverse
        val rev_es1 = rev_es0.head :: 0 :: rev_es0.tail
        val es1 = rev_es1.reverse
        pq.enqueue((value(es1), es1))
        
        if(es0.forall(0 !=))
            pq.enqueue(g.next)
        next_value(es0).foreach(es => pq.enqueue((value(es), es)))
        
        v0
    }
    
    def next_value(es :List[Int]) = {
        def f(es :Option[List[Int]]) :Option[List[Int]] = es match {
            case Some(0 :: 0 :: tail) => None
            case Some(0 :: e :: tail) => Some(e :: 0 :: tail)
            case Some(e :: tail) => f(Some(tail)).map(e :: _)
            case _ => None
        }
        
        f(Some(es.reverse)) match {
            case Some(a) => Some(a.reverse)
            case None => None
        }
    }
}

def find_solution(it :Iterator[Long], prev :Long, counter :Int = 0) :Long =
    if(counter == L)
        prev - L + 1
    else {
        val v = it.next
        if(v != prev + 1)
            find_solution(it, v, 1)
        else
            find_solution(it, v, counter + 1)
    }

def solve() = {
    val it :Iterator[Long] = new gen_numbers(L)
    println (find_solution(it, 0L))
}

object Test extends Benchmark {
    def run() = solve
}

val L = 4
println (Test.runBenchmark(10))