# Prime Numbers: Sieve of Eratosthenes

My training wheels implementation of Sieve of Eratosthenes to generate prime numbers.

```
/**
* Find prime numbers using Eratosthenes Sieve.
* Scala Gods - this is neither functional nor scala except the syntax.
* Think pseudocode that actually compiles and works.
*/
object EratosthenesSieve extends App {
val primes = getPrimes(1000)
println(primes.mkString(" ,"))
def getPrimes(x: Int) : Seq[Int]= {
//We use a single dimension array, we will use the index as the number.
val sieve = new Array[Int](x)
//we will flip these to 0 as we traverse. Initially, every number is prime.
for (i <- 0 to sieve.size-1) sieve(i) = 1
//This is our pivot. We leave sieve(0) and sieve(1) alone. Sieve(2) has number 2 which is our first prime number.
var pivot = 2
while(pivot <= (x-1)/pivot){
//we start with the pivot, and mark all its multiples except itself as non-prime.
//we do this till we reach the end of the array
for(i <- 2 to (x-1)/pivot){
sieve(pivot*i) = 0 //not prime
}
//now we find the next pivot which is the next in the array which is 1
pivot = nextPivot(pivot,sieve)
}
//filter our the primes, we use some real scala here, sorry. Kinda tired.
for(s<-2 to sieve.size-1; if(sieve(s)==1)) yield(s)
}
def nextPivot(currentPivot:Int, x:Array[Int]) : Int = {
//return the next pivot, which is the next index after currentPivot that is 1
var nextPivot = currentPivot+1
var done = false
while(!done){
if(x(nextPivot)==1) done = true
else nextPivot += 1
}
nextPivot
}
}
```