CODEWITHSUNDEEP
ruby-on-railsrubyprimes
swapab
swapab

Reputation: 2410

Ruby: find left truncatable primes between 10 to 9999(efficiently)

As the title says. I want to find all left truncatable primes between 10 and 9999 using Ruby language. Following is what I tried and it gives me the result.

require 'prime'
require 'benchmark'

trunc_primes = []

Benchmark.bmbm do |bm|
  bm.report{
    Prime.each(10000).each do |num|
      is_tunc_prime = true
      (1..(num.to_s.length)).to_a.reverse.each do |i|
        factor = 10 ** i
        unless num.divmod(factor)[1].prime?
          is_tunc_prime = false
          break
        end
      end
      trunc_primes << num if is_tunc_prime
    end;nil
  }
end

Question: Can this script be optimized further(lesser loops, use formula rather than factor division technique) ?

Benchmark stats:

➜  truncatable git:(master) ✗ ruby truncatable_primes.rb
Rehearsal ------------------------------------
   0.000000   0.000000   0.000000 (  0.000026)
--------------------------- total: 0.000000sec

       user     system      total        real
   0.000000   0.000000   0.000000 (  0.000020)
➜  truncatable git:(master) ✗ ruby truncatable_primes.rb
Rehearsal ------------------------------------
   0.000000   0.000000   0.000000 (  0.000024)
--------------------------- total: 0.000000sec

       user     system      total        real
   0.000000   0.000000   0.000000 (  0.000017)
➜  truncatable git:(master) ✗ ruby truncatable_primes.rb
Rehearsal ------------------------------------
   0.000000   0.000000   0.000000 (  0.000028)
--------------------------- total: 0.000000sec

       user     system      total        real
   0.000000   0.000000   0.000000 (  0.000044)
➜  truncatable git:(master) ✗ ruby truncatable_primes.rb
Rehearsal ------------------------------------
   0.000000   0.000000   0.000000 (  0.000030)
--------------------------- total: 0.000000sec

       user     system      total        real
   0.000000   0.000000   0.000000 (  0.000019)

Benchmark above script and Amadan's script

Rehearsal ------------------------------------------
mine     0.020000   0.000000   0.020000 (  0.022804)
Amadan   0.000000   0.000000   0.000000 (  0.001559)
--------------------------------- total: 0.020000sec

           user     system      total        real
mine     0.020000   0.000000   0.020000 (  0.019625)
Amadan   0.000000   0.000000   0.000000 (  0.001540)

Upvotes: 3

Views: 102

Answers (1)

Amadan
Amadan

Reputation: 198418

Since you're already using Prime, why invent hot water?

Prime.each(10000).reject { |p| p < 10 }.select { |p|
  s = p.to_s
  1.upto(s.length - 1).all? { |i|
    s[i] != '0' && Prime.prime?(s[i .. -1].to_i)
  }
}

EDIT: This can actually be optimised further though - if ABCD turns out not to be a truncatable prime, ZABCD does not need to be tested:

require 'set'
require 'prime'
Set.new.tap { |f|
  Prime.each(10000) { |p|
    s = p.to_s
    f << p if p < 10 || (s[1] != '0' && f.include?(s[1 .. -1].to_i))
  }
}.reject { |p| p < 10 }

EDIT: Forgot about the no zeroes requirement. Added. But being on mobile now, can't check if still running OK.

Upvotes: 4

Related Questions