计算质数和回文数的小程序
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; }