Find the sum of all the primes below two million

I’d say this is the first of the problems Greg and I have tackled that would really benefit from the kind of optimisations we’ve both added to our previous solutions. The Ruby solution below would take *an age* to complete:

sumofprimesbelowrange = 2

def isPrime(num)

i = 2

while i<num

if num%i == 0

return false

end

i=i+1

end

end

while range > 1

if isPrime(range) != false

sumofprimesbelowrange=sumofprimesbelowrange+range

end

range=range-1

end

puts "Sum of all primes below #{range}"

puts "is #{sumofprimesbelowrange}"

### improvements

If a *number A* (in our range) can be divided to a whole by *number B*, then it stands that the result of that division will also fail. The next example still takes a long time to return:

counter = 2

sumofprimesbelowrange = 2

def isPrime(num)

i = 2

while 2*i<num

if num%i == 0

return false

end

i=i+1

end

end

while counter < range

if isPrime(counter) != false

puts counter

sumofprimesbelowrange=sumofprimesbelowrange+counter

else

end

counter=counter+1

end

puts "Sum of all primes below #{counter}"

puts "is #{sumofprimesbelowrange}"

### Odds

We also know that the 2 is the only even prime number, so we can ignore all even numbers above 2 completely:

if num%2==0

return false;

end

i = 2

while 2*i<num

if num%i == 0

return false

end

i=i+1

end

end

After a little reading into primes, the method I’m using is known as trial division. A further available optimisation allows us to only examine any division up to the square root of the number we’re checking. So our routine can be amended such:

if num%2==0

return false;

end

i = 2

while i*i<=num

if num%i == 0

return false

end

i=i+1

end

end

This small change has a big effect, reducing the running time of the script to a matter of a few minutes.

This weeks challenge has been the most interesting yet, I now have lots of additional reading to do on the other possible solutions.