Skip to content

Instantly share code, notes, and snippets.

@onilton

onilton/sieve.scala

Last active April 5, 2017 18:29
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 onilton/44f1faf1f4ae6b4d413fba826b44caa2 to your computer and use it in GitHub Desktop.
Save onilton/44f1faf1f4ae6b4d413fba826b44caa2 to your computer and use it in GitHub Desktop.
Download ZIP
Sieve of
Raw
sieve.scala
def sieve(maxNumber: Int) = {
def innerSieve(p: Int, n: Int, a: Array[Boolean]): Array[Boolean] =
if (p >= a.size) a
else if (!a(p) || n >= a.size) innerSieve(p+1, 2*(p+1), a)
else { a(n) = false ; innerSieve(p, p + n, a) }
innerSieve(2, 2, Array.fill(maxNumber+1)(true)).zipWithIndex.filter(_._1).map(_._2)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment