Raymond Camden is a developer evangelist for Adobe. His work focuses on web standards, mobile development and Cold Fusion. He's a published author and presents at conferences and user groups on a variety of topics. He is the happily married proud father of three kids and is somewhat of a Star Wars nut. Raymond can be reached via his blog at www.raymondcamden.com or via email at raymondcamden@gmail.com Raymond is a DZone MVB and is not an employee of DZone and has posted 244 posts at DZone. You can read more from them at their website. View Full User Profile

# Thursday Code Puzzler: Sieve of Eratosthenes

01.17.2013
| 5288 views |

It's been a long time since I posted a Puzzler, but as I was perusing Khan's CS courses this morning (which look really cool!) I came across this fascinating discourse on prime numbers: Sieve of Eratosthenes.

Your challenge today is simple - watch the video (via the link above or embed below) - and once the theory is discussed, do not look at the full solution. Write up a solution in your language of choice and post your answer below. You can also use a Gist or Pastebin link.

Published at DZone with permission of Raymond Camden, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

### Vijay Nathani replied on Thu, 2013/01/17 - 1:17pm

Groovy

```def allPrimesTill (maximum) {
def (primes, number, allNumbers) =[ [], 0, new LinkedList(2..maximum) ]
while (allNumbers) {
if (allNumbers.first() * allNumbers.first() >= maximum) { primes.addAll(allNumbers); break }
for (int i=number * number; i <= maximum; i+=number)
allNumbers.remove((Object)i)
}
primes
}
assert allPrimesTill(10) == [2,3,5,7]
```

### sun east replied on Fri, 2013/01/18 - 4:26am

```scala> def primesToN(n: Int): Seq[Int] = {
|   def sieve(xs: Seq[Int]): Seq[Int] = xs match {
|     case Seq()   => Seq()
|     case p +: rs => p +: sieve(rs diff (p*p to n by p))
|   }
|   sieve(2 to n)
| }
primesToN: (n: Int)Seq[Int]

scala> primesToN(20)
res0: Seq[Int] = List(2, 3, 5, 7, 11, 13, 17, 19)```

### Jim Passmore replied on Wed, 2013/01/23 - 6:56pm

python

[2, 3, 5, 7]

```from math import sqrt
def sieve(max):
# create array
primes = []
for num in range(2,max+1):
primes.append(num)
index=0
while primes[index] <= sqrt(max):
for j in range(primes[index]*primes[index], max+1, primes[index]):
try:
primes.remove(j)
except:
pass
index += 1
return primes

if __name__ == '__main__':
primes = sieve(10)
print primes```