RでProject Euler 1〜5

Rを勉強しなくてはならなくなったので練習のためにProject Eulerの問題を解いてみます。

Problem 1

ふつうに手続き型で書くこともできます。

N <- 1000
s <- 0
for(n in 1:N-1) {
    if(n %% 3 == 0 || n %% 5 == 0) {
        s <- s + n
    }
}
print(s)

1:3で(1, 2, 3)というベクトルを生成します。
剰余は%%なんですね。

ベクトルを一度に操作することもできます。

N <- 1000
v <- 1:N-1
w <- replace(v, which(v%%3!=0 & v%%5!=0), 0)
print(sum(w))

3でも5でも割り切れないとき0にします。
andはなぜか&なんですよね。

Problem 2

N <- as.integer(4e6)
a <- 0
b <- 1
s <- 0
while(b <= N) {
    if(b %% 2 == 0) {
        s <- s + b
    }
    tmp <- b
    b <- a + b
    a <- tmp
}
print(s)

特に問題ないですよね。遅延評価とかできないので、こういう風に書かざるを得ないですよね。

Problem 3

max_prime_factor <- function(n, p) {
    while(p * p <= n) {
        if(n %% p == 0) {
            return(max_prime_factor(n / p, p))
        }
        p <- p + 1
    }
    return(n)
}

N <- 600851475143
print(max_prime_factor(N, 2))

再帰もふつうに使えます。

Problem 4

digits <- function(n) {
    v <- c()
    while(n > 0) {
        d <- n %% 10
        v <- append(v, d)
        n <- (n - d) / 10
    }
    return(v)
}

is.palindromic <- function(n) {
    ds <- digits(n)
    L <- length(ds)
    for(k in 1:(L%/%2)) {
        if(ds[k] != ds[L-k+1]) {
            return(FALSE)
        }
    }
    return(TRUE)
}

add.sorted <- function(M, lh, rh) {
    m <- lh * rh
    
    f <- function() {
        for(k in 1:length(v)) {
            if(m < v[k]$MUL) {
                return(k - 1)
            }
        }
        return(k)
    }
    
    M2 <- rbind(M, c(lh, rh, m))
    M3 <- M2[order(M2[,3], decreasing=T),]
    return(M3)
}

N <- 1000
M <- matrix(c(N - 1, 1, N - 1, 1, (N - 1) * (N - 1), 1), nrow=2, ncol=3)
while(TRUE) {
    v <- M[1,]
    n <- v[3]
    if(is.palindromic(n)) {
        print(n)
        break
    }
    x <- v[1]
    y <- v[2]
    if(y == N - 1) {
        M <- add.sorted(M, x - 1, y)
    }
    if(x < y) {
        M <- add.sorted(M, x, y - 1)
    }
    M <- M[-1,]
}

ベクトルに要素を追加するにはappendを使います。
整数の除算は、%/%を使います。ふつうに/を使って割り切れなかったら、実数になってしまいます。
RにはPriorityQueueなどというものは無いようなので、行列で代用しています。被乗数、乗数、積を列にして、新たに要素を追加するときは、rbindで最後に追加して、3列目でソートします。取り出すときは頭から取り出します。

Problem 5

gcd <- function(n, m) {
    if(m == 0) {
        return(n)
    }
    else {
        return(gcd(m, n %% m))
    }
}

lcm <- function(n, m) {
    return(n / gcd(n, m) * m)
}

N <- 20
s <- 1
for(n in 1:N) {
    s <- lcm(s, n)
}
print(s)

特に問題ないですね。