文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >计算质数和回文数的小程序

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

作者头像
大江小浪
发布于 2018-07-25 10:00:05
发布于 2018-07-25 10:00:05
9860
举报
文章被收录于专栏：小狼的世界小狼的世界

Ruby 代码如下

代码语言：javascript
复制
   1:  def isZhishu?(num)
代码语言：javascript
复制
   2:      count = 2
代码语言：javascript
复制
   3:      while count < num do
代码语言：javascript
复制
   4:          return false if ( num % count ) == 0
代码语言：javascript
复制
   5:          count = count + 1
代码语言：javascript
复制
   6:      end
代码语言：javascript
复制
   7:   
代码语言：javascript
复制
   8:      return true
代码语言：javascript
复制
   9:  end
代码语言：javascript
复制
  10:   
代码语言：javascript
复制
  11:  def isHuiwen?(num)
代码语言：javascript
复制
  12:      s = num.to_s.reverse.to_i
代码语言：javascript
复制
  13:      return true if num == s
代码语言：javascript
复制
  14:   
代码语言：javascript
复制
  15:      return false
代码语言：javascript
复制
  16:  end
代码语言：javascript
复制
  17:   
代码语言：javascript
复制
  18:  count = 0
代码语言：javascript
复制
  19:  10000.times{ |i|
代码语言：javascript
复制
  20:      i = i + 1
代码语言：javascript
复制
  21:      if isZhishu?(i) && isHuiwen?(i) then
代码语言：javascript
复制
  22:          printf "%4d", i
代码语言：javascript
复制
  23:          print "\n"
代码语言：javascript
复制
  24:          count = count + 1
代码语言：javascript
复制
  25:      end
代码语言：javascript
复制
  26:  }
代码语言：javascript
复制
  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整除，所以不需要考虑。

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

具体代码如下：

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

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2012-05-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
小程序

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

小程序
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论