締め切りが 2月26日(金)10:00 AM なので,
2月26日(金)10:01 AM に公開されるように,自動投稿
それにしても,締め切りまで長いわ~~
最寄りの素数
【概要】
下図のように、1以上のすべての整数をならべます。
入力で指定された数に最も近い素数を求めてください。
【入力と出力】
入力は
14
のような形で、標準入力から来ます。
普通に10進数です。素数が来ることはありません。
出力は、入力の最寄りの素数です。
最寄りの素数が複数ある場合は、小さい順にコンマ区切りで出力してください。
入力が14のときの出力は
7,13,23
になります。
ブルートフォースで何とかなる。
f = function(n=1000000, range=7) {
k = floor(sqrt(n)-1e-10)+1
mx <- (k+range)^2
tbl <- 1:mx
tbl[1] <- 0
for (i in 2:floor(sqrt(mx))) {
if (tbl[i]) {
mx2 <- mx %/% i
tbl[2:mx2*i] <- 0
}
}
mid = k^2-k+1
nx = ifelse(n > mid, k^2-n+1, k)
ny = ifelse(n > mid, k, n-(k^2-2*k+2)+1)
Min = .Machine$integer.max
M = D2 = NULL
for (k2 in k+(-range:range)) {
mid = k2^2-k2+1
for (m in max(1, k2^2-2*k2+2):max(1, k2^2)) {
if (tbl[m]) {
mx = ifelse(m > mid, k2^2-m+1, k2)
my = ifelse(m > mid, k2, m-(k2^2-2*k2+2)+1)
d2 = (nx-mx)^2+(ny-my)^2
if (Min >= d2) {
Min = d2
M = c(M, m)
D2 = c(D2, d2)
}
}
}
}
cat(M[D2 == Min], sep=",")
}
con = file("stdin", "r"); f(as.integer(readLines(con, 1)))
※コメント投稿者のブログIDはブログ作成者のみに通知されます