# Project Euler #10 in Ruby - summation of primes

I'd like to have some feedback as to the performances of the algorithm.

class Sumprime
attr_accessor :number

def initialize(number)
self.number = number
prime_serie
end

def is_prime?(num)
counter = 2
root_num = Math.sqrt(num).ceil
while counter <= root_num
if num % counter == 0 && num != counter
return false
break
else
counter += 1
end
end
return true
end

def percentage_prime
((prime_serie.size / number.to_f) * 100)
end

def prime_serie
prime_array = [1]
counter = 2
while counter < number
if is_prime?(counter)
prime_array << counter
counter += 1
end
counter += 1
end
prime_array.inject(:+)
end
end

• Practically all optimizations will sacrifice memory for computation time. Even your trial division method could be sped up by storing a list of primes you already have found and iterating through them rather than $[2, \sqrt{n}]$. – twohundredping May 6 '15 at 16:15

## 1 Answer

Instead of checking whether each number from 2 until n is prime, you could generate all the primes that are less or equal to n using an algorithm like the Sieve of Eratosthenes.

A trivial implementation of the sieve in ruby is:

def sieve(n)
sieve = []
root = Math.sqrt(n)
(3..root).step(2) do |i|
if !sieve[i]
(i**2..n).step(i) do |j|
sieve[j] = true
end
end
end
[2] + (3..n).step(2).select{ |i| !sieve[i] }
end


Thus, your code could be rewritten as:

class NewSumprime
attr_accessor :number

def initialize(number)
self.number = number
end

def sieve(n)
sieve = []
root = Math.sqrt(n)
(3..root).step(2) do |i|
if !sieve[i]
(i**2..n).step(i) do |j|
sieve[j] = true
end
end
end
[2] + (3..n).step(2).select{ |i| !sieve[i] }
end

def prime_serie
sieve(number).inject(&:+)
end
end


A simple benchmark on my PC gives:

ts = Time.now.to_f ; Sumprime.new(1000000).prime_serie ; Time.now.to_f - ts
=> 11.137484788894653
ts = Time.now.to_f ; NewSumprime.new(1000000).prime_serie ; Time.now.to_f - ts
=> 0.493511438369751

• @Snowbody Project Euler 10 requires a list of all primes less than two million. If you were to use a deterministic primality test on each number independently then you would end up double testing $92\%$ of the numbers. Are you sure that outweighs the sieve? – twohundredping May 4 '15 at 18:28
• So don't use a deterministic primality test on each number. Instead use a modified sieve that's more efficient than basic Eratosthenes. There's a segmented sieve with wheel factoring that's much more efficient. – Snowbody May 4 '15 at 18:56
• The Sieve of Eratosthenes gives you all the primes, but it's not the most efficient. By using a bit of number theory, there are a few prime-generating functions that are much more efficient. – Snowbody May 4 '15 at 18:58
• (i**2..n).step(i) do |j| sieve[j] = true end generates all the number that are not prime. could you tell me more about this block : [2] + (3..n).step(2).select{ |i| !sieve[i] } – Cyzanfar May 5 '15 at 9:10
• @Cyzanfar The first block generates an array where the position j in the array is true if the number is not prime. So the code you're asking about converts this array of true and nil into an array of numbers, we reject the positions that are true so we end up with an array of prime numbers. The [2] + part prepends number 2 into our array of primes – egwspiti May 5 '15 at 9:16