Prime Factorisation in Swift

Question

I made a playground to try find prime factors of any given number, and it works, and I'm happy with the first function, even if not correctly named - I don't know what to name it.

My main need for improvement is in the second half. I can't for the life of me think of a way of looping through a list until the functions output is constant. I thought of recursion, but I didn't understand it. This is what I came up with, and I'd like to see how I can improve it because it's sloppy and ugly.

import UIKit

func primeFact(tree: [Int]) -> Array<Int> {
    var newTree = tree
    for element in newTree{
        for divisor in 2..<element{
            if element%divisor == 0{
                newTree = newTree.filter { $0 != element}
                newTree+=[(element/divisor),divisor]
                break
            }
        }
    }
    return newTree
}

var initial = primeFact(tree: [992])
var temp = [Int]()
while true {
    if primeFact(tree: initial) == initial{
        break
    }
    temp = primeFact(tree: initial)
    initial = temp
}
print(primeFact(tree: initial))

Answer 1

To address your "main need" first: Your algorithm starts with a single-element array, and then repeatedly calls primeFact() to compute a new array, until the array is "constant". That can be done more clearly as

var initial = [992]
var temp = [Int]()
repeat {
    temp = initial
    initial = primeFact(tree: temp)
} while initial != temp
print(initial)

However, your algorithms seems to be highly inefficient, for the following reasons:

• Since the trial division starts with the lowest possible divisors, each found divisor is necessarily a prime number. But the next call to primeFact() will again try to find divisors of that number.
• All calls to primeFact() will try all numbers starting from 2 as divisors for all elements in the "tree". For example, if the current list is [2, 2, <someOddNumber>] then each call will again try to divide <someOddNumber> by 2.
• A lot of intermediate arrays are created.
• Possible large arrays must be compared in order to determine if the factorization is done.

Additional remarks:

• Put spaces around operators, e.g. element % divisor for better readability.
• Use either [Int] or Array<Int> for array notation (I prefer the first), but don't mix it.
• Calling the parameter tree is confusing because you treat it as an array, not as a tree.

A more efficient approach is to divide the given number by 2, 3, 4, ... As soon as a factor is found, the number is divided by this factor. Using the fact that composite number \$ n > 1 \$ must have a prime factor \$ p \$ for which \$ p \le \sqrt n \$, this leads to the following function:

func primeFactors(_ n: Int) -> [Int] {
    var n = n
    var factors: [Int] = []

    var divisor = 2
    while divisor * divisor <= n {
        while n % divisor == 0 {
            factors.append(divisor)
            n /= divisor
        }
        divisor += divisor == 2 ? 1 : 2
    }
    if n > 1 {
        factors.append(n)
    }

    return factors
}

As another small optization, only 2 and all odd numbers are used as trial divisors.

Performance comparison:

• For \$ N = 1000000000000 = 2^{12} \cdot 5^{12} \$: Your tree factorization: 1ms. Direct factorization: 0.005 ms.
• For \$ N = 1000000000001 = 73 \cdot 137 \cdot 99990001 \$: Your tree factorization: 1,100ms. Direct factorization: 0.1 ms.

The tests were done on a 1.2 GHz Intel Core m5 MacBook, with the code compiled in Release mode.

Answer 2

import UIKit is superfluous.

Your algorithm is hugely inefficient: you are rebuilding the array many times. Swift Playground says that when factoring 992, the line with newTree = newTree.filter { $0 != element} executes 38 times.

This algorithm doesn't involve rewriting the array, and it also outputs the prime factors in non-decreasing order.

func primeFactors(n: Int) -> Array<Int> {
    var n = n
    var factors = [Int]()
    for divisor in 2 ..< n {
        while n % divisor == 0 {
            factors.append(divisor)
            n /= divisor
        }
    }
    return factors
}

print(primeFactors(n: 992))