Project Euler #12 in Swift - Highly divisible triangular number 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) -&gt; 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 &lt; smallest ? smallest : maxFactor
    for factor in smallest...maxFactor {
        if toFactor.isMultipleOf(factor) {
            primesFactor[factor] = (primesFactor[factor] ?? 0) + 1
            return findPrimesFactorFrom(factor, toFactor / factor, &amp;primesFactor)
        }
    }

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

func highlyDivisibleTriangularNumber() -&gt; Int {

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

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

    while OverNumberOfDivisors &gt;= currentNumberOfDivisors {

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

        findPrimesFactorFrom(2, triangleNumber, &amp;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:() -&gt; ()) {
    let startTime = CFAbsoluteTimeGetCurrent()
    operation()
    let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
    println("Time elapsed : \(timeElapsed) s")
}

printTimeElapsedWhenRunningCode(euler12)


The code executes in 0.3s
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) -&gt; Int {

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

    do {
        number++
        triangleNumber += number
        currentNumberOfDivisors = countDivisors(triangleNumber)
    } while currentNumberOfDivisors &lt; 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) -&gt; [Int : Int] {
    var factors : [Int : Int] = [:]
    var factor = 2

    while factor * factor &lt;= 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 &gt; 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) -&gt; 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) -&gt; Int {

    var numDivisors = 1
    var factor = 2

    while factor * factor &lt;= 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 &gt; 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) -&gt; Int {

    var n = 1
    while (countDivisors((n+1)/2) * countDivisors(n) &lt; requiredDivisors) {
        n++;
        if (countDivisors(n/2) * countDivisors(n+1) &gt;= requiredDivisors) {
            break;
        }
        n++;
    }
    let triangleNumber = n*(n+1)/2
    return triangleNumber
}


which runs in 0.006 seconds on my computer.