2008-05-26 Ruby 测试题(00017)

jmouse

UID: 3919
帖子: 130
积分: 299
在线时间: 23 小时

1^# jmouse 发表于 2008-05-26 13:54

2008-05-26 Ruby 测试题(00017)

F(n) = 1 + 2 + ,..., + n = (1+n)*n/2
求最小的n，使F(n)拥有超过500个的约数。

本题取自php?name=Euler" onclick="tagshow(event)" class="t_tag">Euler-12，不难，但求一个效率解。

5swords

UID: 39285
帖子: 1
积分: 2
在线时间: 10 分钟

2^# 5swords 发表于 2008-05-26 14:33

Euler12我做的是6s, 源码在11页上面.

jmouse

UID: 3919
帖子: 130
积分: 299
在线时间: 23 小时

3^# jmouse 发表于 2008-05-26 16:25

比我快许多啊，受制约与求约数的方法，后面好几道题目都失控与效率。

5swords

UID: 39285
帖子: 1
积分: 2
在线时间: 10 分钟

4^# 5swords 发表于 2008-05-26 16:48

这一题做了好长时间, 是由于实现下面的想法的时候引入了一个小BUG.

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

jmouse

UID: 3919
帖子: 130
积分: 299
在线时间: 23 小时

5^# jmouse 发表于 2008-05-27 10:14

啊，prime_division，我嫌判断素数麻烦，所以没用这个。

5swords

UID: 39285
帖子: 1
积分: 2
在线时间: 10 分钟

6^# 5swords 发表于 2008-05-27 10:40

所有的约数都是素数的积, 拿到所有的素数就是所有的约数了啊.
24 = [[2,3],[3,1]]
2**0 * 3**0 , 2**3 * 3**1=> 1 * 24
2**1 * 3**0 , 2**2 * 3**1=> 2 * 12
2**2 * 3**0 , 2**1 * 3**1=> 4 * 6
2**3 * 3**0 , 2**0 * 3**1=> 8 * 3

所有约数的个数: 8 = (3+1) * (1+1)

jmouse

UID: 3919
帖子: 130
积分: 299
在线时间: 23 小时

7^# jmouse 发表于 2008-05-27 16:16

这个我知道，我也是这么算的，只是在分解的时候没有用prime_division而是自己笨来的。

[Copy to clipboard] [ - ]

5swords

UID: 39285
帖子: 1
积分: 2
在线时间: 10 分钟

8^# 5swords 发表于 2008-05-27 16:27

看来我们做过EULER这题的, 在这儿太早讨论有点不好的说...

司马睿风

UID: 8155
帖子: 2
积分: 4
在线时间: 10 分钟

9^# 司马睿风发表于 2008-05-27 21:55

看看6秒怎么算的，为什么我算要半分钟，差距太大了

5swords

UID: 39285
帖子: 1
积分: 2
在线时间: 10 分钟

10^# 5swords 发表于 2008-05-28 13:50

重构了一下我的程序, 可能做one liner有点过了:

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