約数の個数

指数表記を使わずに整数を素因数分解する。たとえば，72 = 2*2*2*3*3 のように表現する。このときに使う乗算記号 "*" の数は 4 つ。
4 桁の数の「各桁の和」が「素因数分解した "*" の数」と等しくなるものを列挙せよ。

基本的には，約数の個数を求めること（乗算記号の数は約数の数から 1 をひいたもの）。

以下のプログラムの実行時間は 0.542 秒

prime = c(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
               71,73,79,83,89,97)
func = function(n) {
  Sum = sum(as.integer(unlist(strsplit(as.character(n), ""))))
  Count = 0
  for (j in prime) { # 97 までの素数を調べれば十分
    repeat {
      if (n == 1 || n %% j) break
      Count = Count+1
      n = n %/% j
    }
  }
  if (n != 1) Count = Count+1
  return(Sum == Count-1)
}

for (i in 1000:9999) {
  if (func(i)) print(i)
}

gmp を使って無精をすれば以下のように簡単に書ける。この実行時間は 0.300 秒

library(gmp)
for (i in 1000:9999) {
  Count = length(as.character(factorize(i)))-1
  Sum = sum(as.integer(unlist(strsplit(as.character(i), ""))))
  if (Count == Sum) print(i)
}

答：以下の 13 個の整数

[1] 1001
[1] 1010
[1] 1040
[1] 1110
[1] 1300
[1] 1400
[1] 1600
[1] 2010
[1] 2304
[1] 3100
[1] 3120
[1] 4200
[1] 8000

階乗の約数の個数

2!，3!，4!，…，305! をそれぞれ素因数分解したときに，「2 が素因数として出てくる個数」と「2 ではない素数が素因数として出てくる個数の和」が一致するものがいくつあるか

たとえば，7! を考える場合，2, 3, 4, 5, 6, 7 それぞれの数について，2 とそれ以外の約数が何個ずつあるか数える。7! の約数はそれを全部合計すればよい。 8! の約数は，7! の約数に 8 の約数を加える。以下順に。

prime = c(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,
157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,
241,251,257,263,269,271,277,281,283,293)
twos = others = numeric(305)
for (i in 2:305) {
  n = i
  t = 0 # 約数 2 の個数
  repeat {
    if (n %% 2) break
    t = t+1
    n = n %/% 2
  }
  twos[i] = t
  for (j in prime) {
    if (n == 1) break
    o = 0 # 2 以外の約数の個数
    repeat {
      if (n %% j) break
      o = o+1
      n = n %/% j
      if (n == 1) break
    }
    others[i] = others[i]+o
  }
}
twos = cumsum(twos)[-1]
others = cumsum(others)[-1]
(2:305)[twos == others]

3!,  7!, 11!, 13!, 14!, 18!, 20! の 7 個（くそおもしろくもない。なんで 305 までにしたんだ？）

所要時間は 0.053 秒

gmp を使って手抜きをすれば，以下のように簡単に記述できる。所用時間も 0.259 秒となり，ほどほどだ。

library(gmp)
for (i in 2:305) {
  x = table(as.character(factorize(factorialZ(i))))
  if (sum(x)/2 == x["2"]) print(i)
}