2
\$\begingroup\$

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))
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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) \$\endgroup\$ – Mr. Xcoder Jun 25 '17 at 17:32
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin R Jun 24 '18 at 9:07
  • \$\begingroup\$ Addendum: Looking for prime factors could be sped up by only looking for numbers off by 1 from a multiple of 6. \$\endgroup\$ – ielyamani Dec 9 '18 at 20:03
4
\$\begingroup\$

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))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.