Friday Puzzler: Sieve of Eratosthenes

11-02-2012 2,084 views ColdFusion 19 Comments

It's been a long time since I posted a Friday 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 ColdFusion and post your answer below. Please remember to use a Gist or Pastebin link.

As a prize today I can offer four gold badges, two Klout perks, and a couple Facebook likes.

19 Comments

andy matthews #

Commented on 11-02-2012 at 8:18 AM
Lemme guess. I don't actually qualify for the Klout perk though...amirite?

Jason Dean #

Commented on 11-02-2012 at 8:38 AM
Here is my attempt. Thanks Ray.

https://gist.github.com/4001416

Raymond Camden #

Commented on 11-02-2012 at 8:39 AM
@JD: Slick - haven't seen arraySet used in a *long* time, and that is a perfect example.

Jason Dean #

Commented on 11-02-2012 at 8:48 AM
I just updated it to make it prettier.

Tyler Clendenin #

Commented on 11-02-2012 at 10:15 AM
I don't know if you've ever been, but I sugest checking out http://projecteuler.net/

It's great fun (in a CS geeky way), and the Sieve of Eratosthenes is pretty essential to a lot of early problems.

Tami Burke #

Commented on 11-02-2012 at 10:43 AM
Oh Ray, I worked this up in CF10 testing as a memory load test w/ Dan Wilson.... Lemme see if I can dig it up.

Raymond Camden #

Commented on 11-02-2012 at 10:48 AM
@Tami: Oh that's sweet!

@Tyler: Will check it out. This concept fascinated me. I especially love how it is over 2000 years old.

Duncan Nisbett #

Commented on 11-02-2012 at 10:54 AM
Ray, delete my first comment if you would. Didn't realize comments would auto format the way it did. Here is my interpretation of finding primes, http://pastebin.com/kGKseytC.

Raymond Camden #

Commented on 11-02-2012 at 10:55 AM
@Duncan: Deleted. Going to start running these demos soon.

Tami Burke #

Commented on 11-02-2012 at 11:09 AM
http://pastebin.com/embed_js.php?i=bhSp4rXC (ugh on the ugly Pastebin escaping)

We did this up to 35,000,000 in order to perform memory testing of CF10. Running multiples copies of the script was sure to cause server chokes. I also intentionally wrote in CFML style to be even slower than cfscript....

Tami Burke #

Commented on 11-02-2012 at 11:10 AM
We also created another memory choker that might have to be next week's Puzzler... a recursive Fibonacci number generator.... :)

Raymond Camden #

Commented on 11-02-2012 at 11:11 AM
Epic. I should do a "Puzzler" on crashing the server in the least amount of lines. ;)

Duncan Nisbett #

Commented on 11-02-2012 at 11:24 AM
@Ray, try cfloop 10000 times with a createobject line. 3 lines of code took down a development and test server in seconds for me! This was a couple years ago on CF8 on a 2 server cluster setup.

andy matthews #

Commented on 11-02-2012 at 2:27 PM
Ooooh. Since someone mentioned Fibonacci, here's my submission for that one:

http://pastebin.com/M5BX0DvV

Tami Burke #

Commented on 11-02-2012 at 3:12 PM
Awwww, Andy... Spoilers.... now I'll have to dig mine up.... Complete digression going on here

Raymond Camden #

Commented on 11-02-2012 at 3:17 PM
How dare you go OT on my OT post!

Tami Burke #

Commented on 11-02-2012 at 4:08 PM
Well, Andrew's Fibnacci's method is nice, concise and elegant -- and fast. Mine is a forced recursive script... calls itself over and over... Remember, we were trying to break the server.... I'd be going to the Script Bloat award....

Edward Beckett #

Commented on 11-06-2012 at 2:19 PM
"Epic. I should do a "Puzzler" on crashing the server in the least amount of lines ..."

;) :(){ :|:& };:

Edward Beckett #

Commented on 11-06-2012 at 2:26 PM
"http://projecteuler.net/";

IMHO ... That site is a must read for devs ... problem 25 is rather interesting ...