In preparation for some interviews (do you know of a great company in Portland, OR? Let me know!), I’ve been studying various algorithms and rebuilding my Big(O) notation musculature. The Sieve of Eratosthenes is a simple algorithm for calculating primes with O(n log n) complexity when implemented with regular loops.
The algorithm is really simple: take a list of numbers and then let P equal 2. Iterating until you have gone past the end of the list, take P multiplied by 2,3,4,5, etc, and mark those numbers as composite numbers. Once you have marked the composites which are multiples of P in the list, look for the first number past P: this is a prime, and the next value of P. Then, repeat the process again and again until P is larger than the size of the list. All unmarked values are the prime numbers.
As I’ve been studying the various algorithms, I like to start with some tests to verify that my final code works. AngularJS makes writing testable JS code so easy. Here is my test:
My test generates a list of numbers, then runs the algorithm. I check
to see that 5 is prime, and that 8 is not prime. I verify that the
first and second primes in the primes cache are 3 and 5, and that the
last one is 97. I cheated by following along using this
example. I use
$timeout inside the implementation code to slow down the algorithm
for human consumption, but in the tests I don’t need that, so I mocked
out timeout so it just immediately runs the callback.
After some thought, it makes sense to have two algorithsm, one with
the timeouts to delay execution for doing the animations, and
anothe pure algorithm implemented strictly with loops. These two
should produce the same results, so the tests are identical. You can
see one of the algorithms is called
SieveOfE and one is called
SieveOfEwoT (“without the timeout”).
Once I had these tests, I could run karma test runnner against them,
and run until my tests passed. You can find the karma config file in the gist
which contains all the files (run it with the command
karma start karma.js).
The code to do the sieve turned out to be surprisingly compact. I’m sure that is all CoffeeScript’s fault.
AngularJS handles most of the work here, rebuilding the DOM with the
proper CSS once a new calculation has completed. I wanted to really
make it pop, so to speak, so I added a CSS3 explosion animation.
AngularJS makes this so easy: when you use
ng-class any new classes
added after a
$digest cycle also include a special class with the
-add postfix. I added an animation inside of
.prime-add to make
those primes pop out of the page when the prime was found. This only
works on Chrome and other webkit browsers, because I am too lazy to
add two other prefixes.
ng-if="0 != $index")
To play with all this yourself, make sure you have ruby and nodejs installed; then clone the gist and then run these commands:
$ coffee -c e.coffee # compile to JS for running in the browser $ powder link # make sure you have the powder gem and pow.cx installed $ open http://9965127.dev/e.html