Return to Revisions

Improving your factors function

Your factors() function seems works correctly, as far as I can see. There is a theoretical risk of rounding errors since a 64-bit IEEE floating point number with its 53-bit significant cannot represent all large integers precisely. But as long as your numbers are below \2ドル^{53} = 9007199254740992\$, you are on the safe side.

The name is a bit misleading: The function does not determine the factors of a numbers but the count of factors, better names might be countFactors or countDivisors.

The function is very inefficient however. It can be improved a bit with small effort, but there are much better algorithms (more below).

First note that

(1...iroot).map({n % 0ドル})

creates an array of length iroot with all the remainders. Then

.filter({0ドル == 0})

creates another array with all remainders which are zero. Creating (and disposing of) these arrays takes time (and memory), but all you are interested is the final count. Therefore an explicit loop is more efficient:

func factors(_ n: Int) -> Int {
 let root = Double(n).squareRoot()
 let iroot = Int(root)
 
 var count = 0
 for i in 1...iroot {
 if n.isMultiple(of: i) {
 count += 2
 }
 }
 if Double(iroot) == root {
 count -= 1
 }
 return count
}

A better algorithm

An efficient method to determine the number of divisors of an integer (and I'm repeating arguments from Getting the divisors count of an integer now) is to use the prime factorization: If $$ n = p_1^{e_1} ,円 p_2^{e_2} \cdots p_k^{e_k} $$ is the factorization of \$ n \$ into prime numbers \$ p_i \$ with exponents \$ e_i \$, then $$ \sigma_0(n) = (e_1+1)(e_2+1) \cdots (e_k+1) $$ is the number of divisors of \$ n \$, see for example Wikipedia: Divisor function. Example: $$ 720 = 2^4 \cdot 3^2 \cdot 5^1 \Longrightarrow \sigma_0(720) = (4+1)(2+1)(1+1) = 30 ,円 . $$

A possible implementation (taken from Project Euler #12 in Swift - Highly divisible triangular number and updated for Swift 4+) is

func countDivisors(_ n : Int) -> Int {
 var n = n
 var numDivisors = 1
 var factor = 2
 while factor * factor <= n {
 if n % factor == 0 {
 var exponent = 0
 repeat {
 exponent += 1
 n /= factor
 } while n % factor == 0
 numDivisors *= exponent + 1
 }
 factor = factor == 2 ? 3 : factor + 2
 }
 if n > 1 {
 numDivisors *= 2
 }
 return numDivisors
}

Benchmarks

Running the code with an upper bound of \10,000,000ドル\$ (on a MacBook Air, compiled in Release configuration):

• With your original factors function: 49 seconds.
• With the improved factors function: 13 seconds.
• With the countDivisors function: 3 seconds.

Further suggestions

I may be advantageous to compute all prime numbers (up to the square root of the upper bound) in advance, for example with the Sieve of Eratosthenes.

Then you can use these prime numbers as trial divisors in the countDivisors function instead of trying all odd numbers.