Solution to SPOJ problem PRIME1 using Futures

SPOJ-PRIME1-UsingFutures.scala

import collection.immutable.HashMap
import Stream.cons
import java.io.{BufferedWriter, PrintWriter}
import Console.{readInt, readLine}
import Math.{sqrt, ceil}
import concurrent.ops.future
import concurrent.FutureTaskRunner
import actors.scheduler.ExecutorScheduler
import java.util.concurrent.Executors.newFixedThreadPool
import java.util.concurrent.CountDownLatch
import Runtime.getRuntime

/*
 My solution to SPOJ problem PRIME1 (https://www.spoj.pl/problems/PRIME1/) in Scala.
 Unfortunately it takes more time than expected and hence fails in SPOJ submission.
 */
object Main {

  def main(arguments: Array[String]) {
    // val start = System.nanoTime
    val writer = new BufferedWriter(new PrintWriter(System.out))

    val runner: FutureTaskRunner = ExecutorScheduler(
      newFixedThreadPool(getRuntime availableProcessors), true)
    val noOfTestCases: Int = readInt
    val countDownLatch = new CountDownLatch(noOfTestCases)
    val primeList = for {
      i <- 1 to noOfTestCases
      val input = readLine.trim.split(" ")
    } yield future({
      val primes = primesBetween(input(0) toInt, input(1) toInt)
      countDownLatch.countDown()
      primes              
    })(runner)

    primeList foreach {primes =>
      primes() foreach { x: Int => writer.write("%s\n".format(x)) }
      writer.write("\n")
      writer.flush
    }
    countDownLatch.await
    runner.shutdown
    writer.flush
    // System.out.println("time taken = %s sec".format((System.nanoTime - start)/1e9))
  }

  /*
    Finds prime numbers between <code>start</code> and <code>end</code>.
   */
  def primesBetween(start: Int, end: Int) = {
    // println("primesBetween(%s, %s)".format(start, end))
    val firstCandidate = start match {
      case 1 => 3
      case 2 => 3
      case x => x match {
        case y if isPrime(y) => y
        case y if y % 2 == 0 => y + 1
        case y => y + 2
      }
    }

    lazy val candidates: Stream[Int] = cons(firstCandidate, candidates map { _ + 2 })
    lazy val realCandidates = if (start == 1 || start == 2) {
      cons(2, candidates)
    } else candidates
    realCandidates filter isPrime takeWhile { _ <= end } force
  }

  private val odds: Stream[Int] = cons(3, odds map { _ + 2 })
  private val primes: Stream[Int] = cons(2, odds filter isPrime)

  val isPrime = memoize {
    (n: Int) => {
      // println("isPrime(%s)".format(n))
      n match {
        case 1 => false
        case 2 => true
        case 3 => true
        case 5 => true
        case 7 => true
        case x => x match {
          // case y if y % 2 == 0 => false
          case y if y % 3 == 0 => false
          case y if y % 5 == 0 => false
          case y if y % 7 == 0 => false
          case y if !((y + 1) % 6 == 0 || (y - 1) % 6 == 0) => false
          case y => primeDivisors(y) isEmpty
        }
      }
    }
  }

  private val primeDivisors = memoize {
    (n: Int) => {
      // println("primeDivisors(%s)".format(n))
      primes takeWhile { _ <= ceil(sqrt(n))} filter {n % _ == 0 }
    }
  }

  def memoize[X,R](f: X => R) = {
    var cache = new HashMap[X,R];
    { (x: X) => {
      if (cache contains x) cache.get(x).get
      else synchronized {
        val fx = f(x)
        cache = cache + (x -> fx)
        fx
      }
    }}
  }

}