2008-03-21 测试题(00004)

转自php?name=Project" onclick="tagshow(event)" class="t_tag">Project php?name=Euler" onclick="tagshow(event)" class="t_tag">Euler Problem 7
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
求质数，一个经典的东西，也是一个典型的可以群魔乱舞的东西。

先看完题目!

第10001个质数是104743,不好意思.

$arr=[ ] #建立一个全局数组 $arr
$arr[0]=2
def add_prime(n) #定义方法 将 n以内的奇素数加入$arr
  3.step(n,2){|num|$arr <<num if is_prime?num }
end
def is_prime?(number) #定义方法 判断一个数是否是素数
 j=0 #数组下标
   while $arr[j] * $arr[j] <=number
   return false if number % $arr[j] ==0
   j +=1
   end
 return true
end
add_prime(1000000)
print $arr[10001]

xavier方法可以改进的是2.upto(self**0.5)，完全可以只考虑奇数。
loop里连续考虑2次是个很新奇的想法，把3的倍数考虑进去了，不错。

3楼的答案是错误的，为什么错我们看4楼就知道了，数组从0开始用的。
顺便说一句，我也很喜欢用$arr，is_prime?(number)，握手先。不过，我希望太熟悉的注释就不要出现了。

也说一下4楼的程序，除了在0上稍有瑕疵之外，最重要的是，有什么理论能知道第10001个质数是小于1000000的？这个很致命。

看看老大的答案

一直不明白~~

楼上不明白啥