範囲が100万もあるときは総当たりなんかやったらダメってことだな。
さっきのも参考にしてたんだけど、Wikipediaのオイラーのφ関数 - Wikipediaによれば、nが
というように素因数分解できるとき、
といった具合にを求めることができる。問題はが最大になるnを求めろというものだったので、今の式を変形した
を最小にする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]