Return to Answer

• Project Euler Problem 12 - triangle number with 500 divisors

• Project Euler Problem 12 - triangle number with 500 divisors

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
}

The variable names (prime, exponent) might be more descriptive than (index, factor) in your code.

The main advantage is that it now becomes "obvious" that those two methods can be combined into one, without storing the factors and exponents in an intermediate dictionary:

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
}

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:

I would make the required number of divisors (500) 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 requiredDivisors >= currentNumberOfDivisors
 
 return triangleNumber
}
func euler12() {
 let number = highlyDivisibleTriangularNumber(500)
 println(number)
}

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
}

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)
}

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
}