Skip to content

Instantly share code, notes, and snippets.

@tnoda
Last active August 29, 2015 14:00
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 tnoda/11086124 to your computer and use it in GitHub Desktop.
Save tnoda/11086124 to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes in Scala
import scala.annotation._
import scala.collection.mutable.ArrayBuffer
object PrimeNumber {
def apply(n: Int = 1000000): Array[Int] = sieve(n)
def sieve(n: Int): Array[Int] = {
val primes = new ArrayBuffer[Int]
val isPrime = Array.fill(n + 1)(true)
@tailrec
def loop(i: Int): Unit = {
@tailrec
def innerLoop(j: Int): Unit = {
if (j > n) ()
else {
isPrime(j) = false
innerLoop(j + i)
}
}
if (i > n) ()
else {
if (isPrime(i)) {
primes += i
innerLoop(i * 2)
}
loop(i + 1)
}
}
loop(2)
primes.toArray
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment