回答編集履歴
2
第二の選択を追加
answer
CHANGED
|
@@ -33,10 +33,27 @@
|
|
|
33
33
|
やっていることは[末尾呼び出し最適化](https://ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0#.E6.9C.AB.E5.B0.BE.E5.91.BC.E5.87.BA.E3.81.97.E6.9C.80.E9.81.A9.E5.8C.96)という手法です。詳細は下記の記事を参考にしてください。
|
|
34
34
|
[Ruby で末尾呼び出し最適化する方法 - おもしぇてっく](https://omoshetech.com/tail-call-optimization-in-ruby/)
|
|
35
35
|
|
|
36
|
-
|
|
36
|
+
末尾呼び出し最適化は卑怯だ…でもやり方は変えたくないと言うのであれば、単純に次の約数を見つけるとすればいいかと思います。次の呼び出しは約数が見つかったときだけでもいいのですから。
|
|
37
37
|
|
|
38
38
|
```Ruby
|
|
39
39
|
# frozen_string_literal: true
|
|
40
|
+
def divisors_all(m)
|
|
41
|
+
divisors_all_r(m, 1, [])
|
|
42
|
+
end
|
|
43
|
+
|
|
44
|
+
def divisors_all_r(m, k, divisors)
|
|
45
|
+
d = (k..m).find { |i| m % i == 0 }
|
|
46
|
+
return divisors unless d
|
|
47
|
+
divisors_all_r(m, d + 1, divisors + [d])
|
|
48
|
+
end
|
|
49
|
+
|
|
50
|
+
p divisors_all(10000)
|
|
51
|
+
```
|
|
52
|
+
|
|
53
|
+
ただ、今回の「全ての約数を求める」ということだけが条件であれば、素因数分解して、全ての組合せをかけた物をリストにした方がいいかもしません。
|
|
54
|
+
|
|
55
|
+
```Ruby
|
|
56
|
+
# frozen_string_literal: true
|
|
40
57
|
require 'prime'
|
|
41
58
|
|
|
42
59
|
def divisors_all(m)
|
1
Integer#prime_divisionを使うことに
answer
CHANGED
|
@@ -40,7 +40,7 @@
|
|
|
40
40
|
require 'prime'
|
|
41
41
|
|
|
42
42
|
def divisors_all(m)
|
|
43
|
-
[1].product(*
|
|
43
|
+
[1].product(*m.prime_division.map { |n, e| (0..e).map { |i| n**i } })
|
|
44
44
|
.map { |list| list.inject(:*) }
|
|
45
45
|
.sort
|
|
46
46
|
end
|