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.

• Mr. Xcoder: 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)
• Martin R: @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.
• ielyamani: Addendum: Looking for prime factors could be sped up by only looking for numbers off by 1 from a multiple of 6.

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