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.
