約数の個数

指数表記を使わずに整数を素因数分解する。たとえば，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