计算质数和回文数的小程序

Ruby 代码如下

   1:  def isZhishu?(num)
   2:      count = 2
   3:      while count < num do
   4:          return false if ( num % count ) == 0
   5:          count = count + 1
   6:      end
   7:   
   8:      return true
   9:  end
  10:   
  11:  def isHuiwen?(num)
  12:      s = num.to_s.reverse.to_i
  13:      return true if num == s
  14:   
  15:      return false
  16:  end
  17:   
  18:  count = 0
  19:  10000.times{ |i|
  20:      i = i + 1
  21:      if isZhishu?(i) && isHuiwen?(i) then
  22:          printf "%4d", i
  23:          print "\n"
  24:          count = count + 1
  25:      end
  26:  }
  27:  print "\n\nTotal:#{count}"

.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }

上面这个方法非常笨重,时间复杂度是 O(n^2),可以进行一些优化。根据 @sdpfoue 的建议,做了优化。

首先就是可以只对大于3的奇数进行检查,因为偶数肯定可以被2整除,所以不需要考虑。

另外循环相除的时候,可以只除以质数,这样也能够减少不少步骤。但是会增加空间的消耗,就是所谓的用空间换时间。

具体代码如下:

   1:  def isZhishu?(num, arrZhishu)
   2:      return true if num == 1 || num == 2
   3:      count = 2
   4:   
   5:      if( arrZhishu.empty? )then
   6:          #count = 2
   7:          while count < num do
   8:              return false if ( num % count ) == 0
   9:              if( count >= 11 ) then
  10:                  count = count + 2 # Only judge even numbers
  11:              else
  12:                  count = count + 1
  13:              end
  14:          end
  15:   
  16:          return true
  17:      else
  18:          arrZhishu.each{|value|
  19:              next if value == 1
  20:              return false if ( num % value ) == 0
  21:          }
  22:          return true
  23:      end
  24:  end
  25:   
  26:  def isHuiwen?(num)
  27:      s = num.to_s.reverse.to_i
  28:      return true if num == s
  29:   
  30:      return false
  31:  end
  32:   
  33:  count = 0
  34:  arrZhishu = Array.new
  35:  i = 0
  36:  while i < 10000000 do
  37:      if i >= 11 then
  38:          i = i + 2
  39:      else
  40:          i = i + 1
  41:      end
  42:   
  43:      if isZhishu?(i, arrZhishu) && isHuiwen?(i) then
  44:          arrZhishu.push(i)
  45:          #printf "%4d", i
  46:          #print "\n"
  47:          count = count + 1
  48:      end
  49:  end
  50:  print "\n\nTotal:#{count}"

.csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券