What Is the Most Efficient Way of Finding All the Factors of a Number in Python

What is the most efficient way of finding all the factors of a number in Python?

from functools import reduce

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

This will return all of the factors, very quickly, of a number n.

Why square root as the upper limit?

sqrt(x) * sqrt(x) = x. So if the two factors are the same, they're both the square root. If you make one factor bigger, you have to make the other factor smaller. This means that one of the two will always be less than or equal to sqrt(x), so you only have to search up to that point to find one of the two matching factors. You can then use x / fac1 to get fac2.

The reduce(list.__add__, ...) is taking the little lists of [fac1, fac2] and joining them together in one long list.

The [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 returns a pair of factors if the remainder when you divide n by the smaller one is zero (it doesn't need to check the larger one too; it just gets that by dividing n by the smaller one.)

The set(...) on the outside is getting rid of duplicates, which only happens for perfect squares. For n = 4, this will return 2 twice, so set gets rid of one of them.

Faster Way To Find Factors of n only using the math library

EDIT: Just like @John Coleman said in the comment of this solution, it's better to obtain the factors while you're calculating the primes, so you can avoid extra work in case you finish factorizing the number before the sieve is finished. The updated code would be:

def factors(number):
    n=int(number**.5)+1
    x=number
    divisors=[]
    era =[1] * n
    primes=[]
    for p in range(2, n):
        if era[p]:
            primes.append(p)
            while x%p==0:
                x//=p
                divisors.append(p)
            for i in range(p*p, n, p):
                era[i] = False
    if x!=1:
        divisors.append(x)    
    return divisors

OG Solution:

Get the prime factors between 2 and sqrt(n) with the Erathostenes Sieve and after it, check which ones are divisors of n. That will reduce hugely the running time of your code.

The Erathostenes sieve doesn't use more than lists, operations %,>=,<= and booleans.

Here's a shorter implementation than the one in the link I shared you:

def factors(number):
    n=int(number**.5)+1
    era =[1] * n
    primes=[]
    for p in range(2, n):
        if era[p]:
            primes.append(p)
            for i in range(p*p, n, p):
                era[i] = False
    divisors=[]
    x=number
    for i in primes:
        while x%i==0:
            x//=i
            divisors.append(i)
    if x!=1:
        divisors.append(x)    
    return divisors

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

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]

List all factors of number

You can refer this code:

def find_factor(n):
  factor_values = []
  for i in range(1, n + 1):
    if n % i == 0:
      factor_values.append(i)

  values = ""
  for v in factor_values:
    values += str(v) + " "

  return values

The function will return 1 2 3 6

Most efficient way to find all factors with GMPY2 (or GMP)?

I just made some quick changes to your code to eliminate redundant name lookups. The algorithm is still the same but it is about twice as fast on my computer.

import gmpy2
from gmpy2 import mpz

def factors(n):
    result = set()
    n = mpz(n)
    for i in range(1, gmpy2.isqrt(n) + 1):
        div, mod = divmod(n, i)
        if not mod:
            result |= {mpz(i), div}
    return result

print(factors(12345678901234567))

Other suggestions will need more information about the size of the numbers, etc. For example, if you need all the possible factors, it may be faster to construct those from all the prime factors. That approach will let you decrease the limit of the range statement as you proceed and also will let you increment by 2 (after removing all the factors of 2).

Update 1

I've made some additional changes to your code. I don't think your all_multiplies() function is correct. Your range() statement isn't optimal since 2 is check again but my first fix made it worse.

The new code delays computing the co-factor until it knows the remainder is 0. I also tried to use the built-in functions as much as possible. For example, mpz % integer is faster than gmpy2.f_mod(mpz, integer) or gmpy2.f_mod(integer, mpz) where integer is a normal Python integer.

import gmpy2
from gmpy2 import mpz, isqrt

def factors(n):
    n = mpz(n)

    result = set()
    result |= {mpz(1), n}

    def all_multiples(result, n, factor):
        z = n
        f = mpz(factor)
        while z % f == 0:
            result |= {f, z // f}
            f += factor
        return result

    result = all_multiples(result, n, 2)
    result = all_multiples(result, n, 3)

    for i in range(1, isqrt(n) + 1, 6):
        i1 = i + 1
        i2 = i + 5
        if not n % i1:
            result |= {mpz(i1), n // i1}
        if not n % i2:
            result |= {mpz(i2), n // i2}
    return result

print(factors(12345678901234567))

I would change your program to just find all the prime factors less than the square root of n and then construct all the co-factors later. Then you decrease n each time you find a factor, check if n is prime, and only look for more factors if n isn't prime.

Update 2

The pyecm module should be able to factor the size numbers you are trying to factor. The following example completes in about a second.

>>> import pyecm
>>> list(pyecm.factors(12345678901234567890123456789012345678901, False, True, 10, 1))
[mpz(29), mpz(43), mpz(43), mpz(55202177), mpz(2928109491677), mpz(1424415039563189)]

---

Related Topics