Problem 69

Problem 69 - Project Euler
答は出たけど20分くらいかかってしまう…
だめだ別の方法考えないと。

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

euler.phi <- function(n){
  ans <- n
  num <- n
  i <- 1
  while(sqrt(n) >= p.lis[i]){
    frag <- FALSE
    repeat{
      if(num%%p.lis[i]==0){
        num <- num/p.lis[i]
        frag <- TRUE
       }else{
        break
      }
     }
    if(frag) ans <- ans*(1-1/p.lis[i])
    i <- i + 1
  }
  if(num == 1){
    ans
  }else{
    ans * (1 - 1/num)
  }
}

for(i in 1:(10^6)){
  if(i/euler.phi(i) > n.div.phi){
    n.div.phi <- i/euler.phi(i)
    ans <- i
  }  
}