Project Euler #10 in Ruby - summation of primes

Question

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
– twohundredping, Commented May 6, 2015 at 16:15

egwspiti · Accepted Answer · 2015-05-04 12:11:49Z

2

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

answered May 4, 2015 at 12:11

egwspiti

1361 bronze badge

2

\$\begingroup\$ @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? \$\endgroup\$

twohundredping
– twohundredping

2015-05-04 18:28:13 +00:00
Commented May 4, 2015 at 18:28
\$\begingroup\$ 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. \$\endgroup\$

Snowbody
– Snowbody

2015-05-04 18:56:40 +00:00
Commented May 4, 2015 at 18:56
\$\begingroup\$ 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. \$\endgroup\$

Snowbody
– Snowbody

2015-05-04 18:58:58 +00:00
Commented May 4, 2015 at 18:58
\$\begingroup\$ (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] } \$\endgroup\$

Cyzanfar
– Cyzanfar

2015-05-05 09:10:40 +00:00
Commented May 5, 2015 at 9:10
1

\$\begingroup\$ @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 \$\endgroup\$

egwspiti
– egwspiti

2015-05-05 09:16:25 +00:00
Commented May 5, 2015 at 9:16

| Show 2 more comments

Stack Exchange Network

Project Euler #10 in Ruby - summation of primes

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Project Euler #10 in Ruby - summation of primes

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions