Instantly share code, notes, and snippets.

# guildenstern70/Eratostene.scala Created Sep 11, 2013

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 } }
to join this conversation on GitHub. Already have an account? Sign in to comment