Get All Primes

The challenge

Given a number: max, find all the primes that are smaller or equal to it. Sum of them up, then return the sum.

One way to do it:

Get/write yourself a function to check if a number is a prime. Then use it to check all numbers equal or smaller than the max

Then the challenge would essentially become: how do you implement the algorithm to check if a number is prime?

A more interesting way: Sieve Of Eratosthenes:

Once you have found a prime number, you can pretty much eliminate a lot of not primes by multiplying that prime with a series of numbers.

Ex: starting from number 2, you can 2X2=4 which eliminates 4, 2X3=6 which eliminates 6, 2X4 which eliminates 8, etc...

A picture is worth small loan of a million dollar:

For more detail:

Wikipedia's article on Sieve Of Eratosthenes

Test it with a huge max

Go to: lib/spec.js change 'xit' to 'it' to see what would happen if generating all the primes within 1 million

Brain Fried Yet? Here are some additional resources

Use regular expression for primality test

link

More on Sieve Of Eratosthenes

Khan Academy Explanation of Sieve of Eratosthenes

Why Prime Numbers are Awesome

Prime Numbers & The Sieve of Eratosthenes

Recent advan-sie(v)es

Researcher Modifies Sieve of Eratosthenes To Work With Less Physical Memory Space

Khan Academy Trial Division Lecture

Trial division