# 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]) -> 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)) ## 2 Answers 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. • I noticed that this line: divisor = divisor == 2 ? 3 : divisor + 2 is very odd. You might replace it with divisor += divisor == 2 ? 1 : 2, if you consider it a good practice, because it slightly improves readability (IMO) – Mr. Xcoder Jun 25 '17 at 17:32 • @DaniSpringer: You are “blocking the main thread.” The UI is only updated when program control returns to the main event loop. Longer calculations must be done on a background thread. – Martin R Jun 24 '18 at 9:07 • Addendum: Looking for prime factors could be sped up by only looking for numbers off by 1 from a multiple of 6. – ielyamani Dec 9 '18 at 20:03 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))