素因数分解で和が同じ

素因数分解で和が同じ

締め切りが 2017/06/06 10:00 AM なので，その 1 分後に投稿されるように予約

設問

整数を素因数分解し、分解した素数の和を求めることを考えます。
例えば、36を素因数分解すると2×2×3×3となり、分解した素数の和は 2+2+3+3=10 となります。
また、32を素因数分解すると2×2×2×2×2となり、分解した素数の和は 2+2+2+2+2=10 となります。

このように、分解した素数の和が同じになることがあります。
そこで、分解した素数の和 n が与えられたとき、元の整数がいくつあるかを求めます。
例えば、n = 10 のとき、上記の32, 36以外に21, 25, 30がありますので、全部で5つあります。

標準入力から n が与えられたとき、元の整数がいくつあるかを求め、標準出力に出力してください。
ただし、2≦n≦250とします。

【入出力サンプル】
標準入力
10

標準出力
5

================================================

整数を，素数を要素として持つ複数の部分に分割する問題である。
計算制限時間の条件（1秒未満）を満たせない。
Java で書いても満たせない。
規則性もなし...
お手上げだ。

R では n=140 でも 3.557 秒掛かる。n=250 だと 790.520 秒
Java では n=250 で 3.745 秒掛かる。

Primes = function(mx) {
    tbl = 1:mx
    tbl[1] = 0
    for (i in 2:floor(sqrt(mx))) {
        if (tbl[i]) {
            mx2 = mx%/%i
            tbl[2:mx2 * i] = 0
        }
    }
    tbl[tbl > 0]
}

f = function(n) {
    primes = Primes(n)
    ary = integer(n/2)
    ary[1] = n
    count = n %in% primes
    lastpos = 1
    repeat {
        sum = 0
        for (pos in lastpos:1) {
            a = ary[pos]
            sum = sum + a
            if (a >= 3) {
                break
            }
        }
        if ((ary[1] == 3 || ary[1] == 2) && all(ary[-1] == 2)) {
            cat(count)
            break
        }
        max = 0
        for (p in primes) {
            if (p < a) {
                max = p
            } else if (p > a) {
                break
            }
        }
        ary[pos] = max
        sum = sum - max
        pos = pos + 1
        repeat {
            if (sum <= max) {
                ary[pos] = sum
                lastpos = pos
                break
            } else {
                ary[pos] = max
                sum = sum - max
            }
            pos = pos + 1
        }
        count = count+(ary[pos] %in% primes)
    }
}

system.time(f(40)) # 302, 0.073 sec.
system.time(f(140)) # 466711, 3.557 sec.
> system.time(f(250))
87778708   ユーザ   システム       経過  
   790.520     23.259    808.163