Skip to content

Instantly share code, notes, and snippets.

@ppopoff
Last active October 18, 2016 00:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ppopoff/2b74d85876da8f0138cdf28072b5bc42 to your computer and use it in GitHub Desktop.
Save ppopoff/2b74d85876da8f0138cdf28072b5bc42 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes in scala
import scala.annotation.tailrec
import java.nio.file.{Paths, Files}
import java.nio.charset.StandardCharsets
type Longs = List[Long]
/* Eratosphen */
def eratosphen(targetNumber: Long): Longs = {
require(targetNumber > 2)
@inline def isPrime(current: Long, divisors: Longs) =
!divisors.exists(current % _ == 0)
@tailrec def rec(current: Long, divisors: Longs, output: Longs): Longs =
if (current == targetNumber)
output
else if (isPrime(current, divisors))
rec(current + 1, current::divisors, current::output)
else
rec(current + 1, divisors, output)
rec(2, Nil, Nil)
}
/* Setup, IO*/
val target = 1000000
val timerStart = System.nanoTime
val result = eratosphen(target)
val timerStop = System.nanoTime
val resultString =
result.mkString(s"Prime numbers, time spent ${timerStop - timerStart}: \n",",\n", "\n")
Files.write(
Paths.get("output.txt"),
resultString.getBytes(StandardCharsets.UTF_8))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment