Problem 70 - Project Euler
ううむ。2分かかる。
を最小化という条件から、
- 素因数は少ない
- 素因数は大きい
また、nが素数のときなので
- nは2つ以上の素因数を持つ
ことが分かる。
なので探索は2つの素数の積、かつ素数はよりいくらか大きいもの以下に限った。
といっても2千万通りくらい調べるので時間がかかる…うーん。くらいを探索したらいいんだろうっていうのは想像できるけど根拠がなにもないし。
limit <- sqrt(10^7)*2 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, m){ n*m*(1-1/n)*(1-1/m) } toNum.r <- function(n){ sum(n*10^(0:(length(n)-1))) } options(scipen=3) toDig.sort <- function(n){ toNum.r(as.numeric(sort((strsplit(as.character(n),"")[[1]])))) } ans <- 0 n.div.phi <- 10^7 for(i in p.lis){ for(j in p.lis[p.lis < i]){ e.phi <- euler.phi(i,j) cand <- i*j if(cand > 10^7) next if(toDig.sort(e.phi)==toDig.sort(cand)){ dphi.cand <- cand/e.phi if(n.div.phi > dphi.cand){ ans <- cand n.div.phi <- dphi.cand n <- i m <- j } } } }