Skip to content

Instantly share code, notes, and snippets.

@abhin4v
Created May 16, 2010 13:33
Show Gist options
  • Save abhin4v/402877 to your computer and use it in GitHub Desktop.
Save abhin4v/402877 to your computer and use it in GitHub Desktop.
Solution to SPOJ problem PRIME1 using Futures
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
}
}}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment