jmouse 2008-3-21 10:27
2008-03-21 测试题(00004)
转自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?
求质数，一个经典的东西，也是一个典型的可以群魔乱舞的东西。
**** Hidden Message *****
wscc111 2008-3-21 12:02
是求10001的质数?还是
先看完题目!
zengjinbai 2008-3-21 12:55
第10001个质数是104743,不好意思.
[[i] 本帖最后由 zengjinbai 于 2008-3-21 14:54 编辑 [/i]]
zengjinbai 2008-3-21 12:56
$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 2008-3-21 13:09
**** Hidden Message *****
jmouse 2008-3-21 13:28
xavier方法可以改进的是2.upto(self**0.5)，完全可以只考虑奇数。
loop里连续考虑2次是个很新奇的想法，把3的倍数考虑进去了，不错。
3楼的答案是错误的，为什么错我们看4楼就知道了，数组从0开始用的。
顺便说一句，我也很喜欢用$arr，is_prime?(number)，握手先。不过，我希望太熟悉的注释就不要出现了。
也说一下4楼的程序，除了在0上稍有瑕疵之外，最重要的是，有什么理论能知道第10001个质数是小于1000000的？这个很致命。
feza 2008-3-21 13:34
看看老大的答案
kukully 2008-3-21 14:49
一直不明白~~
jmouse 2008-3-21 17:22
楼上不明白啥
liumuqing 2008-3-21 20:35
**** Hidden Message *****
3秒才出解。。怎么才能更快？
[[i] 本帖最后由 liumuqing 于 2008-3-21 20:38 编辑 [/i]]
jmouse 2008-3-23 02:47
一个很明显但是效果在10001下并不显著的提升。
把number += 1改成number += 2
算法无法精简，但代码可以。
total其实就是answer.size，那个flag的用法也比较晦涩，sqrt既然只有一个地方用到那就没必要另外赋值，我想这点效率应该是由编译器来搞定的吧。
比较短小的写法：
[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)
[/code]
[[i] 本帖最后由 jmouse 于 2008-3-23 02:50 编辑 [/i]]
love8909 2008-3-23 20:04
膜拜中...
drive2me 2008-3-24 10:41
[quote]原帖由 [i]love8909[/i] 于 2008-3-23 20:04 发表 [url=http://www.ruby-lang.org.cn/forums/redirect.php?goto=findpost&pid=12939&ptid=3866][img]http://www.ruby-lang.org.cn/forums/images/common/back.gif[/img][/url]
膜拜中... [/quote]
不急，慢慢了，积累就有了！
bbschat 2008-3-27 17:41
这题忘记贴了
**** Hidden Message *****
优化一下，我机器上大概 2.36 秒的样子
[[i] 本帖最后由 bbschat 于 2008-3-27 18:17 编辑 [/i]]
AllenDang 2008-3-28 16:30
先顶，回家给自己的答案。很喜欢这个板块，一定要坚持下去！
snakeqx 2008-4-3 10:07
看答案，新手无语中，这个问题我会用弱智穷举法写代码。
jmouse的代码非常优雅！！我喜欢！！！！！
[[i] 本帖最后由 snakeqx 于 2008-4-3 10:15 编辑 [/i]]
jayliu 2008-4-7 11:27
看看答案了，发现自己基础太差了
kukully 2008-4-7 19:33
回复 jmouse
因为我原来没有接触过编程，刚接触ruby，而且对算法不熟，所以当时好多看不懂，现在好些了，不过进步很慢...继续加油！
lxf3 2008-6-16 10:29
看看答案了，发现自己基础太差了
xiuce 2008-6-17 14:18
想看看答案
刀光剑影 2008-6-19 17:17
看看.................
keymi 2008-8-20 13:54
104743 我这个算法的速度好慢，跟高手学习高效率的算法中。。。
**** Hidden Message *****
love8909 2008-8-20 19:13
**** Hidden Message *****
线性筛素数，瞬间出解
logoff 2008-8-20 21:56
dddddddddddddddddddd
acnono 2008-8-21 14:34
[code]**** Hidden Message *****[/code][code]>ruby bbs321.rb
第10001个质数为：104743
用时：8.828s
>Exit code: 0[/code]
acnono 2008-8-21 14:36
好像用时间过多...:L
acnono 2008-8-24 01:11
[code]>ruby pe7.rb
第10001个质数为：104743
用时：2.263s
>Exit code: 0[/code]参照JMouse的意见 时间缩小到了小于3秒 高手高高在上 膜拜
sevk 2008-8-30 11:30
104743
2.131236
看来我的CPU算快的。
[[i] 本帖最后由 sevk 于 2008-8-30 11:36 编辑 [/i]]
punkpopb 2008-9-26 02:13
看来我还是很需要实践啊！