Skip to content

Instantly share code, notes, and snippets.

@sortega
Created Aug 14, 2015
Embed
What would you like to do?
Sequential Eratosthenes sieve
class Sieve(maxNumber: Int) {
private val candidates = Array.fill(maxNumber + 1)(true)
def run(): Unit = {
for (index <- 2 to maxNumber) {
if (candidates(index)) {
crossOutMultiples(index)
}
}
}
private def crossOutMultiples(prime: Int): Unit = {
println(s"$prime is prime")
val firstMultiple = prime * 2
for (index <- firstMultiple to maxNumber by prime) {
candidates(index) = false
}
}
}
object Sieve extends App {
val start = System.currentTimeMillis()
new Sieve(maxNumber = 500000).run()
println(s"Spent just ${System.currentTimeMillis() - start} millis")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment