转自Project 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,不好意思.

[ 本帖最后由 zengjinbai 于 2008-3-21 14:54 编辑 ]

$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的？这个很致命。

看看老大的答案

一直不明白~~

楼上不明白啥

本帖隐藏的内容需要回复才可以浏览

3秒才出解。。怎么才能更快？

[ 本帖最后由 liumuqing 于 2008-3-21 20:38 编辑 ]

一个很明显但是效果在10001下并不显著的提升。
把number += 1改成number += 2

算法无法精简，但代码可以。
total其实就是answer.size，那个flag的用法也比较晦涩，sqrt既然只有一个地方用到那就没必要另外赋值，我想这点效率应该是由编译器来搞定的吧。

比较短小的写法：

[Copy to clipboard] [ - ]

CODE:

def Euler7(x)
  $arr=[2]
  num = 1
  ($arr<<num if is_prime?num+=2) while $arr.size < x
  puts num
end
def  is_prime?(number)
  for j in $arr
    return false if number % j == 0
    return true if j > number **0.5
  end
end
Euler7(10001)

[ 本帖最后由 jmouse 于 2008-3-23 02:50 编辑 ]

膜拜中...

引用:

原帖由 love8909 于 2008-3-23 20:04 发表
膜拜中...

不急，慢慢了，积累就有了！

这题忘记贴了

本帖隐藏的内容需要回复才可以浏览

优化一下，我机器上大概 2.36 秒的样子

[ 本帖最后由 bbschat 于 2008-3-27 18:17 编辑 ]

先顶，回家给自己的答案。很喜欢这个板块，一定要坚持下去！