专栏首页小狼的世界计算质数和回文数的小程序

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

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 条评论
登录 后参与评论

相关文章

  • 如何开发YUI3的扩展

    YUI是Yahoo发布的一个JS框架,虽然不如jQuery简单,但是如果你是要做一些复杂的事情的时候,有一个合适量级的框架还是能有用不少。

    大江小浪
  • Codeigniter中对核心类的扩展

    Codeigniter框架提供了实现多个应用Application的方法,如参考资料[2]中描述的,这种方法实际上是在网站目录下存在多个入口文件和Applica...

    大江小浪
  • CodeIgniter 2.1.0 的白屏错误调试

    今天在配置一个CodeIgniter 2.1.0时,遇到白屏,系统报500错误,但是Apache的错误日志中看不到任何错误信息输出。

    大江小浪
  • C#如何快速高效地导出大量数据?

    本文转载:http://www.cnblogs.com/herbert/archive/2010/07/28/1787095.html

    跟着阿笨一起玩NET
  • 使用jQuery的animate方法制作滑动菜单

    周末看Ziv小威的博客《制作滑动条菜单,如何延时处理滑动效果,避免动画卡顿》,参见地址:http://www.cnblogs.com/zivxiaowei/p/...

    八哥
  • 通过欧拉计划学Rust编程(第54题)

    由于研究Libra等数字货币编程技术的需要,学习了一段时间的Rust编程,一不小心刷题上瘾。

    申龙斌
  • Flutter这么火为什么不了解一下呢?(下)

    Note: 如何代码实现有问题,可以依据Github上的lib/main.dart 来检查你的代码。

    Android技术干货分享
  • Flutter Widget框架之旅 顶

    Flutter小部件采用现代反应式框架构建,从React中获得灵感。 中心思想是你从小部件中构建你的UI。 小组件描述了他们的视图在给定其当前配置和状态时应该看...

    南郭先生
  • FFmpeg 工程之路-基础开发概述

    注意:还给老师的c语言还是拿起来吧,重新站到鄙视链的顶端,嘿嘿。编译 helloworld.c

    用户1081422
  • go-指针

    任何程序数据载入内存后,在内存都有他们的地址,这就是指针。而为了保存一个数据在内存中的地址,我们就需要指针变量。

    新人小试

扫码关注云+社区

领取腾讯云代金券