Problem 60 こんどこそ

R Project Euler

Problem 60 - Project Euler
40秒くらい．gmpとigraphを使った．
「任意の順でつなげられる2つの素数」をエッジとして大量に集めて，5つのノードからなる完全グラフを探すという方法を採った．完全グラフのうち和が最少になるものが答えということになる．
ただ問題があって

…まあ，1分以内で終わるからいいか．
きっとちゃんとベクトル同士の処理するように注意したらもうちょっと早くなるんだと思う．もちろんやろうとしたんだけどイマイチうまくいかなかった．

library(gmp)
library(igraph)

limit <- 10000
sievebound <- (limit-1)/2
sieve <- logical(sievebound)
crosslimit <- (floor(sqrt(limit))-1)/2
for(i in 1:crosslimit){
  if(!sieve[i]){
    for(j in seq(2*i*(i+1), sievebound, 2*i+1)){
      sieve[j] <- TRUE
    }
  }
}
prime.list <- c(2, 2*(1:sievebound)[!sieve]+1)

conc <- function(a, b){
  a*10^floor(log(b,10)+1) + b
}
isp.conc <- function(a,b){
  (isprime(conc(a, b)) && isprime(conc(b, a)))
}

count <- 0
prime.1 <- numeric(0)
prime.2 <- numeric(0)
for(i in prime.list[prime.list>2]){
  for(j in prime.list[prime.list < i])
    if(isp.conc(i, j)){
      count <- count + 1
      prime.1[count] <- i
      prime.2[count] <- j
    }
}

con.pairs <- data.frame(prime.1, prime.2)

vers <- data.frame(unique(c(prime.1, prime.2)))

g <- graph.data.frame(con.pairs,directed=FALSE, vers)

ans <- cliques(g, min=5)