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}"
上面这个方法非常笨重，时间复杂度是 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}"
时间： 2024-10-12 19:55:37