Problem 12 on the Project Euler site asks:

What is the value of the first triangle number to have over five hundred divisors?

A triangular number T(n) is defined as \(T(n) = \frac{n(n+1)}{2}\). The R code below consists of a solution, which involves the fact that the number of proper divisors of an integer n can be calculated by first computing a prime factorisation of the number n, e.g. if <\(n = p^aq^b\), where p,q are prime, then the number of proper divisors of n can be calculated as \(d(n) = (a+1)(b+1)\). This solution is extremely slow (mainly due to the naive prime sieving algorithm), and could be speeded up dramatically with a little effort.
*# Sieve of Eratosthenes*

prime.sieve **<-** **function**(n) {

a **<-** seq.int(1,n)

p **<-** 1

M **<-** as.integer(sqrt(n))

**while** ((p **<-** p + 1) <= M) {

**if** (a[p] != 0)

a[seq.int(p*p, n, p)] **<-** 0

}

a[a>1 & a>0]

}

*# Trial Division*

*# Returns the exponents of the prime*

*# factors of n *

*# e.g. if n = p^a*q^b*

*# tdiv(n) will return (a,b)*

tdiv **<-** **function**(n) {

primes **<-** prime.sieve(n)

factors **<-** c()

i **<-** 1

curr **<-** 0

**for** (p **in** primes) {

**while** (n %% p == 0) {

curr **<-** curr + 1

n **<-** n %/% p

}

factors[i] **<-** curr

i **<-** i + 1

curr **<-** 0

}

factors[factors > 0]

}

*# Compute nth triangular number*

T **<-** **function**(n) {

(n*(n+1))/2

}

*## Problem 12*

*# This is a slooow solution*

problem12 **<-** **function**(N) {

n **<-** 0 *# current triangular number Tn*

i **<-** 5 *# \sum_{i=1}^n{i} *

**while** (TRUE) {

n **<-** T(i)

factors **<-** tdiv(n)

**if** (prod(factors+1) >= N) {

**return**(n)

}

i **<-** i + 1

}

}