# Project Euler #12 in Swift – Highly divisible triangular number

Posted on

Problem

I just finished Project Euler #12 in Swift, and since there is not any version yet on Code Review, I would like to have some comments on what I did to try to improve it.

The sequence of triangle numbers is generated by adding the natural
numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7
= 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1

3: 1,3

6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have
over five divisors.

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

``````import Foundation

let OverNumberOfDivisors = 500

extension Int {
func isMultipleOf(factor: Int) -> Bool {
return self % factor == 0
}
}

func findPrimesFactorFrom(let smallest: Int, let toFactor: Int, inout primesFactor:[Int:Int]) {
var maxFactor = Int(sqrt(Double(toFactor)))
maxFactor = maxFactor < smallest ? smallest : maxFactor
for factor in smallest...maxFactor {
if toFactor.isMultipleOf(factor) {
primesFactor[factor] = (primesFactor[factor] ?? 0) + 1
return findPrimesFactorFrom(factor, toFactor / factor, &primesFactor)
}
}

primesFactor[toFactor] = (primesFactor[toFactor] ?? 0) + 1
}

func highlyDivisibleTriangularNumber() -> Int {

var currentNumberOfDivisors = 1
var triangleNumber = 1
var number = 1

var primesFactor:[Int:Int] = [:]

while OverNumberOfDivisors >= currentNumberOfDivisors {

number++
triangleNumber += number
primesFactor = [:]

findPrimesFactorFrom(2, triangleNumber, &primesFactor)

currentNumberOfDivisors = 1
for (index, factor) in primesFactor {
if index != 1 {
currentNumberOfDivisors *= (factor + 1)
}
}
}

return triangleNumber
}

func euler12() {
let number = highlyDivisibleTriangularNumber()

println(number)
}

func printTimeElapsedWhenRunningCode(operation:() -> ()) {
let startTime = CFAbsoluteTimeGetCurrent()
operation()
let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
println("Time elapsed : (timeElapsed) s")
}

printTimeElapsedWhenRunningCode(euler12)
``````

The code executes in 0.3s

Solution

I would make the required number of divisors (500 + 1) a parameter of the
function, and move the computation of the number of divisors into a separate
function:

``````func highlyDivisibleTriangularNumber(requiredDivisors : Int) -> Int {

var triangleNumber = 0
var number = 0
var currentNumberOfDivisors : Int

do {
number++
triangleNumber += number
currentNumberOfDivisors = countDivisors(triangleNumber)
} while currentNumberOfDivisors < requiredDivisors

return triangleNumber
}

func euler12() {
let number = highlyDivisibleTriangularNumber(500 + 1)
println(number)
}
``````

Counting the number of divisors is done via the prime factorization (which is good). Your prime factorization is done recursively and returns a dictionary
of factor/exponent pairs. I would prefer an iterative algorithm:

``````func primeFactorization(var n : Int) -> [Int : Int] {
var factors : [Int : Int] = [:]
var factor = 2

while factor * factor <= n {
if n % factor == 0 {
var exponent = 0
do {
exponent++
n /= factor
} while n % factor == 0
factors[factor] = exponent
}
factor = factor == 2 ? 3 : factor + 2
}
if n > 1 {
factors[n] = 1
}

return factors
}
``````

I prefer the explicit `if n % factor == 0` instead of `if n.isMultipleOf(factor)`
with a custom extension, but that might be a matter of taste.

This gives only a small performance improvement, but the function does
now return the factorization, so you don’t have to pass an `inout` argument.

Also the result cannot contain the factor 1 (as in your method). So counting the number of divisors would simply be

``````func countDivisors(num : Int) -> Int {

var numDivisors = 1
for (prime, exponent) in primeFactorization(num) {
numDivisors *= (exponent + 1)
}
return numDivisors
}
``````

The variable names `(prime, exponent)` might be more descriptive
than `(index, factor)` in your code. As the prime number (the dictionary key)
is not needed in the loop you can also write

``````for (_, exponent) in primeFactorization(num) {
numDivisors *= (exponent + 1)
}
``````

or just

``````for exponent in primeFactorization(num).values {
numDivisors *= (exponent + 1)
}
``````

But actually it is more efficient to combine the prime factorization and
the computation of the number of divisors into a single method, without
storing the factors and exponents in an intermediate dictionary:

``````func countDivisors(var n : Int) -> Int {

var numDivisors = 1
var factor = 2

while factor * factor <= n {
if n % factor == 0 {
var exponent = 0
do {
exponent++
n /= factor
} while n % factor == 0
numDivisors *= exponent + 1
}
factor = factor == 2 ? 3 : factor + 2
}
if n > 1 {
numDivisors *= 2
}

return numDivisors
}
``````

and this is much faster (0.02 instead of 0.14 seconds).

The most performance improvement can be gained by taking advantage of the
special form `n * (n+1)/2` of the triangle numbers, and this are the same
arguments as in

In Swift this would be

``````func highlyDivisibleTriangularNumber(requiredDivisors : Int) -> Int {

var n = 1
while (countDivisors((n+1)/2) * countDivisors(n) < requiredDivisors) {
n++;
if (countDivisors(n/2) * countDivisors(n+1) >= requiredDivisors) {
break;
}
n++;
}
let triangleNumber = n*(n+1)/2
return triangleNumber
}
``````

which runs in 0.006 seconds on my computer.