Problem 69 2回目

範囲が100万もあるときは総当たりなんかやったらダメってことだな。
さっきのも参考にしてたんだけど、Wikipediaオイラーのφ関数 - Wikipediaによれば、nが
 n=\prod_{k=1}^d p_k^{e_k}
というように素因数分解できるとき、
 \varphi (n) = n\prod_{k=1}^d\left(1-\frac{1}{p_k}\right)
といった具合に\varphi(n)を求めることができる。問題はn/\varphi(n)が最大になるnを求めろというものだったので、今の式を変形した
 \frac{\varphi(n)}{n} = \prod_{k=1}^d\left(1-\frac{1}{p_k}\right)
を最小にするnが答になる。式を見ると、素因数が多ければ値が小さくなることがわかる。
というわけで、素数を小さいものから順にかけあわせていって、100万を越える一つ手前の値が答になる。

limit <- sqrt(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
    }
  }
}
p.lis <- c(2, 2*(1:sievebound)[!sieve]+1)

ans <- 1
i <- 1
while(ans < 10^6){
  ans <- ans*p.lis[i]
  i <- i+1
}
ans/p.lis[i-1]