Problem 46

Problem 46 - Project Euler
早いには早いけど，素数のリストをどこまで作ったらいいかよく分からなかった．

is.prime <- function(n){
  if(n == 1) return(FALSE)
  if(n < 4) return(TRUE)
  if(n%%2==0) return(FALSE)
  if(n < 9) return(TRUE)
  if(n%%3==0) return(FALSE)
  r <- floor(sqrt(n))
  f <- 5
  while(f <= r){
    if(n%%f == 0) return(FALSE)
    if(n%%(f+2) == 0) return(FALSE)
    f <- f + 6
  }
  return(TRUE)
}

limit <- 10^6
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)

limit.p <- max(prime.list)
candidate <- 35
while(1){
  if(is.prime(candidate)){
    candidate <- candidate + 2
    next
  }
  cand.s <- (candidate - prime.list)[(candidate-prime.list)>0]
  if(sum(sqrt(cand.s/2)%%1 == 0)==0) break
  candidate <- candidate + 2
  if(candidate > limit.p) break
}