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
}
})