Create a gist now

Instantly share code, notes, and snippets.

Find prime numbers using Eratostene's Sieve
/**
* Eratostene Sieve algorithm
*/
package eratostene
/**
* Find prime numbers using Eratostene Sieve
* @param maxPrime Find primes to maxPrime
* @example
*
val e = new Eratostene(100)
println("Computing...")
e.compute()
println("Done.")
for (prime <- e.primes()) {
println("Prime => " + prime)
}
*
*/
class Eratostene(maxPrime: Int) {
protected val maxVal = maxPrime
protected val sieve = Array.fill[Int](maxPrime)(1)
require(maxPrime > 1)
sieve(0) = 0
sieve(1) = 0
def compute() {
var currentPrime = this.nextPrime(0)
var i = 0
while (currentPrime * currentPrime < this.maxVal) {
i = currentPrime * currentPrime
while (i < this.maxVal) {
this.sieve(i) = 0
i += currentPrime
}
currentPrime = this.nextPrime(currentPrime)
}
}
def primes() : IndexedSeq[Int] = {
for (p <- 0 until this.maxPrime
if (this.sieve(p) == 1))
yield p
}
private def nextPrime(lastPrime: Int): Int = {
var i = lastPrime
var foundIt = false
while ( i <= this.maxVal && !foundIt) {
i += 1
if (this.sieve(i) == 1) foundIt = true
}
return i
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment