140問目！素数列から抜き出してつぶやこう？
締め切りが 2017/05/02 10:00 AM なので，その 1 分後に投稿されるように予約
設問
今週のアルゴリズムも140問目！
「140」といえばTwitterにおけるつぶやきの文字数の上限です。
m 以上 n 以下の素数を一列に並べ、その中から連続した数字列を最長140文字で抜き出したとき、最初と最後の数字が同じで、含まれる数の和が最大になるものを求め、その和を出力してください。
例えば、m = 5, n = 30 のとき、
57111317192329
という数字列の中から、最初と最後の数字が同じで、長いものを抜き出すと、含まれる数の和は
7111317 -> 21
1113171 -> 15
3171923 -> 26
92329 -> 25
232 -> 7
となりますので、最大なのは26です。
標準入力から m と n がスペース区切りで与えられるとき、和の最大値を求め、標準出力に出力してください。
なお、m と n は 1 < m < n < 100000を満たす整数とします。
【入出力サンプル】
標準入力
5 30
標準出力
26
−−−−−−−−−−
素直にプログラムし，なんの最適化もしなかったが，計算時間も制限内に収まっていた
f = function(m, n) {
mx = n # エラトステネスの篩で素数列生成
tbl = 1:mx
tbl[1] = 0
for (i in 2:floor(sqrt(mx))) {
if (tbl[i]) {
mx2 = mx %/% i
tbl[2:mx2*i] = 0
}
}
prime <- tbl[tbl >= m] # m 以上，n 以下の素数
x = as.integer(unlist(strsplit(paste(prime, collapse=""), ""))) # 繋いでばらす
maxSum = 0
for (i in seq_along(x)) {
y = x[i:min(i+139, length(x))] # i 番目から 140 個以内の数字列
z = which(y == x[i]) # 最初と同じ数字のある場所
s = sum(y[1:max(z)]) # 最初から最後の位置までの数字の和
maxSum = max(s, maxSum) # 最大のものを記録
}
cat(maxSum)
}
# s = scan(file("stdin", "r"), quiet=TRUE)
# f(s[1], s[2])
f(5, 30) # 26
f(2, 100) # 204
f(100, 10000) # 930
f(10000, 50000) # 860
f(2, 99999) # 1019
