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.