Most Efficient Way to Find All the Factors of a Number?

Question

Disclaimer: There are similar questions to this one on SO, however they all either don't address the efficiency of an algorithm or are written in a different language. See this answer which talks about efficiency in python and see if it helps you answer my question.

So I need the most efficient way to find all of the factors of any given number that works quickly with very large numbers. I already have several iterations of code that works but takes a very long time to process numbers with more than 6 characters.

Edit: upon request here are some of my non-efficient ways of doing this (error-checking left out for clarity)

Really messy:

    @IBAction func findFactorsButton(_ sender: AnyObject) {
    if let _ = textField.text, !textField.text!.isEmpty {
        counter = 1
        factors = []
        repeat {
            counter += 1
            if Int(textField.text!)! % counter == 0 {
                factors.append(String(counter))
            } else {
                continue
            }
        } while counter != Int(textField.text!)
        factors.removeLast()
        outputLabel.text = factors.joined(separator: ", ")

    } else {
        outputLabel.text = ""
    }
}

Less messy solution (playground):

func calculateFactors(n: Int) -> String {
    var result: String = ""
    for i in 1...n {
        guard n % i == 0  else {continue}
        result += i == 1 ? "1" : ", \(i)"
    }
    print(result)
    return result
}

Answer 1

Most Python methods in the referenced Q&A What is the most efficient way of finding all the factors of a number in Python? use the fact that factors of n come in pairs: if i is a factor then n/i is another factor. Therefore it is sufficient to test factors up to the square root of the given number.

Here is a possible implementation in Swift:

func factors(of n: Int) -> [Int] {
    precondition(n > 0, "n must be positive")
    let sqrtn = Int(Double(n).squareRoot())
    var factors: [Int] = []
    factors.reserveCapacity(2 * sqrtn)
    for i in 1...sqrtn {
        if n % i == 0 {
            factors.append(i)
        }
    }
    var j = factors.count - 1
    if factors[j] * factors[j] == n {
        j -= 1
    }
    while j >= 0 {
        factors.append(n / factors[j])
        j -= 1
    }
    return factors
}

Remarks:

• reserveCapacity is used to avoid array reallocations.
• All factors in the range 1...sqrtn are determined first, then the corresponding factors n/i are appended in reverse order, so that all factors are in increasing order.
• Special care must be taken that for perfect squares, sqrt(n) is not listed twice.

For numbers with up to 8 decimal digits, at most 9,999 trial divisions are needed. Example (on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode):

let start = Date()
let f = factors(of: 99999999)
print("Time:", Date().timeIntervalSince(start) * 1000, "ms")
print("Factors:", f)

Output:

Time: 0.227034091949463 ms
Factors: [1, 3, 9, 11, 33, 73, 99, 101, 137, 219, 303, 411, 657, 803, 909, 1111, 1233, 1507, 2409, 3333, 4521, 7227, 7373, 9999, 10001, 13563, 13837, 22119, 30003, 41511, 66357, 81103, 90009, 110011, 124533, 152207, 243309, 330033, 456621, 729927, 990099, 1010101, 1369863, 3030303, 9090909, 11111111, 33333333, 99999999]

Answer 2

It all depends on your numbers. Here is a great summary:

"How big are your numbers?" determines the method to use:

• Less than 2^16 or so: Lookup table.
• Less than 2^70 or so: Sieve of Atkin. This is an optimized version of the more well known Sieve of Eratosthenes. Edit: Richard Brent's modification of Pollard's rho algorithm may be better in this case.
• Less than 10^50: Lenstra elliptic curve factorization
• Less than 10^100: Quadratic Sieve
• More than 10^100: General Number Field Sieve

So it all becomes a matter of picking algorithms and implementing them in Swift. Since you're saying you need numbers with "6 characters" that implies they are around 2^17 or so. So it's option 2 in that list: Sieve of Atkin or the modification of Pollard's rho.