Project Euler #12 in Swift - Highly divisible triangular number

Question

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

Answer 1

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

• Project Euler Problem 12 - triangle number with 500 divisors

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.