2 ~ n までの整数を素因数分解したとき，約数（素数） p が何個あるか数える。
p = 7 のとき 35 = 5 * 7 なので 1 個，49 = 7 * 7 なので 2 個である。
素朴にプログラムしてみると，以下のようになる（素朴すぎるということがすぐわかる）。
> count_factors0 = function(n, p) {
+ count = 0
+ for (i in 2:n) {
+ while (i %% p == 0) {
+ count = count + 1
+ i = i %/% p
+ }
+ }
+ return(count)
+ }
2 〜 50 の約数 7 の個数は，
> count_factors0(50, 7)
[1] 8
ただし，大きな n に対して求めようとすると，とんでもない時間が掛かる。
> system.time({
+ print(count_factors0(50000000, 7))
+ })
[1] 8333328
ユーザ システム 経過
14.356 0.030 14.386
for ループと while ループの使い方が悪いのだ。以下のようにすれば瞬殺である。
> count_factors2 = function(n, p) {
+ count = 0
+ while (n > 0) {
+ count = count + n %/% p
+ n = n %/% p
+ }
+ return(count)
+ }
> system.time({
+ print(count_factors2(50000000, 7))
+ })
[1] 8333328
ユーザ システム 経過
0.004 0.000 0.004
ちょっとわかりにくいが，以下のように再帰関数で定義するとわかりやすいかな。
> count_factors1 = function(n, p) {
+ if (n == 0) {
+ return(0)
+ } else {
+ return(n %/% p + Recall(n %/% p, p))
+ }
+ }
> system.time({
+ print(count_factors1(50000000, 7))
+ })
[1] 8333328
ユーザ システム 経過
0.005 0.000 0.005
