Euler Problem 10

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:

range  = 1999999
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:

range  = 2000000
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:

def isPrime(num)
  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:

def isPrime(num)
  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.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>