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 } }