My solution to SPOJ problem PRIME1 (https://www.spoj.pl/problems/PRIME1/) in Scala.

input.txt

10
1 100000
10 100010
100 100100
1000 101000
10000 110000
100000 200000
1000000 1100000
10000000 10100000
100000000 100100000
999900000 1000000000

SPOJ-PRIME1.scala

import Stream.cons
import java.io.{BufferedWriter, PrintWriter}
import Console.{readInt, readLine}
import Math.{sqrt, ceil}
import scala.collection.mutable.{HashMap => MHashMap}

/*
 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))
    for (i <- 1 to readInt) {
      // val teststart = System.nanoTime
      val input = readLine.trim.split(" ")
      primesBetween(input(0) toInt, input(1) toInt) foreach {
        x: Int => writer.write("%s\n".format(x))
      }
      writer.write("\n")
      writer.flush
      // System.out.println("test %s: time taken = %s sec".format(i, (System.nanoTime - teststart)/1e9))
    }
    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) = {
    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
      }
    }
    // println("firstCandidate = %s".format(firstCandidate))

    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 }
  }

  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 => {
            //println("primeDivisors(%s)".format(y))
            primeDivisors(y) isEmpty
          }
        }
      }
    }
  }

  private def primeDivisors(n: Int) =
    primes takeWhile { _ <= ceil(sqrt(n))} filter {n % _ == 0 }

  def memoize[X,R](f: X => R) = {
    val cache = new MHashMap[X,R];
    { (x: X) => cache.getOrElseUpdate(x, f(x)); }
  }

}