It's not hard to find all of the factors of a given natural number. Below is a pretty fast python function that can do just that:
(Modified version of Steinar Lima's function, https://stackoverflow.com/a/19578818/5946921)
import itertools as it
def factor(n):
step = 2 if n % 2 else 1
factors = ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if not n % i)
return sorted(set(it.chain.from_iterable(factors)))
I am looking to make a function that can do this more efficiently for very large numbers. I have come up with the following function that does just that:
import itertools as it
def large_factor(n):
primes = []
ranges = []
for prime, factors in it.groupby(primeFactor(n), lambda x: x):
primes.append(prime)
ranges.append(range(len(tuple(factors)) + 1))
primes = primes[::-1]
ranges = ranges[::-1]
z = it.product(*(x for x in ranges))
return sorted(product(a ** b for a, b in zip(primes, q)) for q in z)
I am looking for ways to improve this function. I want it to return the factors in ascending order, without duplicates. Originally, I was hoping I'd be able to have the entire thing be a lazy function (no eager evaluation at all). Unfortunately, I haven't been able to figure out a good way to do this. My approach right now is to get the prime factors from n
, and a list of ranges [0, #primes factors + 1). These lists are then reversed, as this makes sorting easier later. The list of ranges is used to generate tuples that contain the powers that are applied to the prime numbers in the last line.
The following two functions are used in the large_factor()
function:
import math
def primeFactor(n):
''' Generates prime factors of n'''
if n <= 1: return
prime = next((x for x in range(2, math.ceil(math.sqrt(n))+1) if n%x == 0), n)
yield prime
yield from primeFactor(n//prime)
from functools import reduce
from operator import mul
def product(iterable):
''' The product of the items in n '''
return reduce(mul, iterable)
I've tested these functions with timeit, and found that factor()
was significantly faster on small values on n, but on large values of n, large_factor()
was significantly faster. I'm looking for any kind of optimization that can make large_factor()
faster on smaller, or (especially) larger numbers, as well as any other suggestions you might have.