Problem 111

R Project Euler

あまり綺麗なやり方ではないけど思ったより簡単に答えが出た．720ms．
ただgmp使ってる．gmpってPEのためにあるんじゃないかと思うくらいPEの問題解く際には使い勝手が良い．良すぎるので多倍長演算とか素数判定とか素因数分解とかのノウハウが自分の中にさっぱり蓄積されない．2週目はgmp縛りでやらないと…．
あとgmpのisprimeっていうのはミラー・ラビンテスト(ミラー–ラビン素数判定法 - Wikipedia)っていう確率的アルゴリズムを使ってるので細かいことを気にするとアレなのかもしれない．一応isprimeの返り値は0:合成数，1:確率的素数，2:素数となっているので(理屈はよく分からないんだけど)，確率的素数と判定されたときだけ試し割りとかで確実な素数判定すればもっと「きちんと」したものになるのだろうとは思う．

library(gmp)

## 文字ベクトルを数値に
char2num <- function(str){
  as.numeric(paste(str, collapse=""))
}

## n桁の数値のうちn-1個がdの重複な数字
rep1 <- function(n, d){
  nums <- numeric(n * 10)
  cnt <- 1
  for(i in 1:n){
    num <- rep(d, n)
    for(j in 0:9){
      num[i] <- j
      nums[cnt] <- char2num(num)
      cnt <- cnt + 1
    }
  }
  return(nums[log(nums, 10)+1 >= n])
}
## の素数
rep1prime <- function(n, d){
  tmp <- rep1(n, d)
  tmp[isprime(tmp)!=0]
}

## n桁の数値のうちn-2個がdの重複な数字
dig2vec2 <- function(d2){               #100未満の数字の桁をベクトルに
  c(floor(d2/10), d2%%10)
}
rep2 <- function(n, d){
  nums <- numeric(0)
  cnt <- 1
  for(i in 1:(n-1)){
    for(j in (i+1):n){
      num <- rep(d, n)
      for(k in 0:99){
        num[c(i, j)] <- dig2vec2(k)
        nums[cnt] <- char2num(num)
        cnt <- cnt + 1
      }
    }
  }
  return(nums[log(nums, 10)+1 >= n])
}
## の素数
rep2prime <- function(n, d){
  tmp <- rep2(n, d)
  tmp[isprime(tmp)!=0]
}

## S(n, d)を求める
S <- function(n, d){
  tmp <- rep1prime(n, d)
  if(length(tmp)==0) tmp <- rep2prime(n, d)
  sum(tmp)
}

## d=0から9に対しS(n, d)の総和を求める
sum.S <- function(n){
  ans <- 0
  for(d in 0:9){
    ans <- ans + S(n, d)
  }
  return(ans)
}
sum.S(10)