Thursday Code Puzzler: Sieve of Eratosthenes
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.
(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)
Tags:
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