Project Euler #10 in Ruby. Three ways to sum primes below 2 million

Question

Question:

Add all prime numbers smaller than 2,000,000.

The first method is done by deriving own is_prime? method:

# First Method
def is_prime(n)
 if n <= 3
 return n > 1
 elsif (n % 2 == 0 || n % 3 == 0)
 return false
 else
 (5..Math.sqrt(n).ceil).step(6) do |i|
 if (n % i == 0 || n % (i+2) == 0)
 return false
 end
 end
 return true
 end
end
start_time = Time.now
range = 2000000
array_of_primes = []
(1..range).each do |n|
 if is_prime(n)
 array_of_primes << n
 end
end
answer = array_of_primes.inject(:+)
duration = Time.now - start_time
puts "Sum of primes below #{range} is #{answer}. Took #{duration} s to calculate using my first method."

Second Method is using Ruby's Prime.is_prime?(n) method:

# Second Method
require 'prime'
array_of_primes = []
start_time = Time.now
(1..range).each do |n|
 if Prime.prime?(n)
 array_of_primes << n
 end
end
answer = array_of_primes.inject(:+)
duration = Time.now - start_time
puts "Sum of primes below #{range} is #{answer}. Took #{duration} s to calculate using my Ruby's Prime.prime? method."

Third method is the simplest form - by using Ruby's Prime.each(2000000) method

# Third Method - Prime.each
start_time = Time.now
answer = Prime.each(range).inject(:+)
duration = Time.now - start_time
puts "Sum of primes below #{range} is #{answer}. Took #{duration} s to calculate using my Ruby's Prime.each method."

All methods gave the correct answer, but the interesting findings is they have drastically different performance, as shown below are the outputs of duration for the computation from each method.

Sum of primes below 2000000 is 142913828922. Took 3.694159 s to calculate using my first method.
Sum of primes below 2000000 is 142913828922. Took 39.370195 s to calculate using my Ruby's Prime.prime? method.
Sum of primes below 2000000 is 142913828922. Took 0.300214 s to calculate using my Ruby's Prime.each method.

As seen above, Best performing is using Prime.each method. I wonder if it already stores a list of prime numbers therefore it doesn't have to compute that long?

Comparing using my own is_prime method and Prime class' Prime.is_prime?(n) method. The Ruby method is taking suprisingly long time to compute the answer.>30s compare to ~3s. Any thoughts on this observation?

• twohundredping: I'm not a ruby programmer but the principle is straightforward. You are performing unnecessary work by iteratively applying is_prime to each number. Whenever you need a list of contiguous primes less than \$\mathrm{N}\$ it is more efficient to generate a sieve than it is to iterate through \$\mathrm{1}\$ to \$\mathrm{N}\$ testing each number independently.
• Chris Yeung: Thanks @twohundredping the wikipedia article about sieve is interesting, please take my upvote.

Answer 1

You should use implicit looping (filtering):

def primes_below(limit)
 (1..limit).select{|i| Prime.prime?(i)}
end

You should use the built-in profiler:

require 'benchmark'
puts Benchmark.measure{primes_below(limit).inject(:+)}