Prime Factorisation in Swift 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]) -&gt; Array&lt;Int&gt; {
    var newTree = tree
    for element in newTree{
        for divisor in 2..&lt;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))
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, &lt;someOddNumber&gt;] then each call will
again try to divide &lt;someOddNumber&gt; 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&lt;Int&gt; 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 &gt; 1 \$
must have a prime factor \$ p \$ for which  \$ p \le \sqrt n \$,
this leads to the following function:

func primeFactors(_ n: Int) -&gt; [Int] {
    var n = n
    var factors: [Int] = []

    var divisor = 2
    while divisor * divisor &lt;= n {
        while n % divisor == 0 {
            factors.append(divisor)
            n /= divisor
        }
        divisor += divisor == 2 ? 1 : 2
    }
    if n &gt; 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.