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 254 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
| 5405 views |
  • submit to reddit

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

Comments

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 }
		primes.add(number = allNumbers.remove())
		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



Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.