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.