4
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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}]\$. \$\endgroup\$ – twohundredping May 6 '15 at 16:15
2
\$\begingroup\$

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
\$\endgroup\$
  • 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 May 4 '15 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 May 4 '15 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 May 4 '15 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 May 5 '15 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 May 5 '15 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.