# Sieve of Eratosthenes

The Sieve of Eratosthenes is a iterative method of discovering primes in the sequence of natural numbers (positive integers starting with `1`). How it works is that you take each number, starting with `2` since `1` is always a factor of everything, and use it as a factor to eliminate all the numbers that are multiples of it. So, for the natural numbers…

``2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15...``

Starting with `2`, every sucessive second number is eliminated leaving:

``2, 3, _, 5, _, 7, _, 9, __, 11, __, 13, __, 15...``

Next, starting with `3`, every third number is eliminated leaving:

``2, 3, _, 5, _, 7, _, _, __, 11, __, 13, __, __...``

This continues on until you’ve eliminated all multiples of each number and then reach the limit of the numbers your testing, like `15` in the case of this example. The numbers that remain are the prime numbers frome the sequence of numbers you scanned.

Once the very first pass using `2` is complete, you don’t need to test any factors that are `even` numbers because they’re already eliminated.

## Seive game

``````enum SieveSteps {
StartList,
PrintList,
EndList,
Scan,
StartCollect,
DoCollect,
EndCollect,
DropBounce,
Idle
}

let spriteList: Sprite[] = null
let boxSprite: Sprite = null
let boxX = 0
let boxY = 0
let j = 0
let factor = 2
let idleCount = 0
let idleReturn = SieveSteps.Idle
let step = SieveSteps.StartList
let naturals = 0
game.splash("Sieve of Eratosthenes")

game.onUpdateInterval(10, function () {
switch (step) {
case SieveSteps.StartList:
boxY = 5
boxX = 4
naturals = 2
step = SieveSteps.PrintList
break

case SieveSteps.PrintList:
if (boxY + 14 < scene.screenHeight()) {
if (boxX + 16 >= scene.screenWidth()) {
boxX = 4
boxY += 14
} else {
boxSprite = sprites.create(img`
b b b b b b b b b b b b b b b b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b 4 4 4 4 4 4 4 4 4 4 4 4 4 4 b
b b b b b b b b b b b b b b b b
`, SpriteKind.Player)
boxSprite.setBounceOnWall(true)
boxSprite.image.printCenter("" + naturals, 2)
boxSprite.left = boxX
boxSprite.top = boxY
boxX += 17
naturals += 1
music.playTone(Note.C, BeatFraction.Sixteenth)
idleCount = 5
idleReturn = SieveSteps.PrintList
step = SieveSteps.Idle
}
} else {
step = SieveSteps.EndList
}
break

case SieveSteps.EndList:
spriteList = sprites.allOfKind(SpriteKind.Player)
game.showLongText("Scan for primes in the sequence of numbers. The score will show your current factor.", DialogLayout.Center)
step = SieveSteps.Scan
break

case SieveSteps.Scan:
j += factor
if (j < spriteList.length) {
if (spriteList[j].image.getPixel(0, 0) > 0) {
spriteList[j].startEffect(effects.disintegrate, 200)
spriteList[j].image.fill(0)
music.playTone(Note.C5, BeatFraction.Sixteenth)
idleCount = 10
idleReturn = SieveSteps.Scan
step = SieveSteps.Idle
}
} else {
if (factor > 2) {
factor += 2
} else {
factor += 1
}
j = factor - 2
}
if (factor > spriteList.length + 2) {
step = SieveSteps.StartCollect
} else {
info.setScore(factor)
}
break

case SieveSteps.StartCollect:
boxY = 5
boxX = 4
j = 0
step = SieveSteps.DoCollect
break

case SieveSteps.DoCollect:
if (j < spriteList.length) {
if (spriteList[j].image.getPixel(0, 0) > 0) {
if (boxX + 16 >= scene.screenWidth()) {
boxX = 4
boxY += 14
}
spriteList[j].left = boxX
spriteList[j].top = boxY
boxX += 17
music.playTone(Note.FSharp4, BeatFraction.Sixteenth)
idleCount = 10
idleReturn = SieveSteps.DoCollect
step = SieveSteps.Idle
}
j += 1
} else {
idleCount = 2
idleReturn = SieveSteps.EndCollect
step = SieveSteps.Idle
}
break

case SieveSteps.EndCollect:
step = SieveSteps.Idle
music.jumpDown.play()
idleCount = 100
idleReturn = SieveSteps.DropBounce
step = SieveSteps.Idle
break

case SieveSteps.DropBounce:
music.magicWand.play()
for (let box of spriteList) {
box.ay = randint(100, 400)
}
idleCount = -1
step = SieveSteps.Idle
break

case SieveSteps.Idle:
if (idleCount > 0) {
idleCount += -1
} else if (idleCount == 0) {
step = idleReturn
}
break
}
})``````