ruby-on-rails - Ruby:找到 10 到 9999 之间的左截断素数(有效)

Question

正如标题所说。我想使用 Ruby 语言找到 10 到 9999 之间的所有左截断素数。以下是我的尝试，它给了我结果。

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

问题:这个脚本可以进一步优化吗(更少的循环，使用公式而不是因子除法​​技术)？

---

基准统计数据:

➜  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)

---

基准以上脚本和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)

Answer 1

既然您已经在使用 Prime，为什么要发明热水？

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)
  }
}

编辑:这实际上可以进一步优化 - 如果 ABCD 结果不是可截断素数，则不需要测试 ZABCD:

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 }

编辑:忘记了无零要求。添加。但是现在在移动设备上，无法检查是否仍然运行正常。