# Python: Factors of a number

Project Euler often requires the factors of a number to be found, here is the function I have written for that purpose.

def factors(n): fact=[1,n] check=2 rootn=sqrt(n) while check<rootn: if n%check==0: fact.append(check) fact.append(n/check) check+=1 if rootn==check: fact.append(check) fact.sort() return fact

As always any help in speeding up my function would be appreciated. I think it could be improved using a sieve method or by checking if its divisible by 2 first then using check+=2 starting at 3 to improve the speed of the loop by a factor of 2.

Below is a the commented version to help explain what’s going on if it’s not clear.

def factors(n): # 1 and n are automatically factors of n fact=[1,n] # starting at 2 as we have already dealt with 1 check=2 # calculate the square root of n and use this as the # limit when checking if a number is divisible as # factors above sqrt(n) will already be calculated as # the inverse of a lower factor IE. finding factors of # 100 only need go up to 10 (sqrt(100)=10) as factors # such as 25 can be found when 5 is found to be a # factor 100/5=25 rootn=sqrt(n) while check<rootn: if n%check==0: fact.append(check) fact.append(n/check) check+=1 # this line checks the sqrt of the number to see if # it is a factor putting it here prevents it appearing # twice in the above while loop and putting it outside # the loop should save some time. if rootn==check: fact.append(check) # return an array of factors sorted into numerial order. fact.sort() return fact

At the end, you want to do

fact.sort()

return fact

since the sort method just returns None and not the sorted list.

A more efficient method to find all the factors is to find all of the prime factors and then build up all of the factors from that. You can do this by say noticing that if p is prime then p%30 must also be prime or one. Also, p%30 can’t be either a 2, 3, or 5 since 2*3*5 = 30. Using this information, you can reduce the number of divisions you need to perform.

You can see the code for this at http://sage.math.washington.edu/home/mhansen/factor.py

Also, if you like doing Project Euler problems in Python, then you should try using Sage ( http://www.sagemath.org ) which has a lot of this functionality already built in (and much faster since it interfaces with C libraries).

Here’s a variant that uses a generator expression.

def genFactors(n):

“””Generate the factors of an integer.”””

yield 1

for i in xrange(2, n/2 + 1):

if n % i == 0:

yield i

yield n

def factors(n):

“””Return the factors of a integer.”””

return list(genFactors(n))

And a better version of above:

def genFactors2(n):

“””Generate the factors of an integer.”””

yield 1

for i in xrange(2, math.floor(math.sqrt(n))):

if n % i == 0:

yield i

yield n/i

yield n

def factors2(n):

“””Return the factors of a integer.”””

return list(genFactors(n))

Here are some timings. I’ve named my function factors and your function slow_factors in the timings below.

Lots of small factors:

sage: %timeit factors(2**40)

10000 loops, best of 3: 44.2 µs per loop

sage: %timeit slow_factors(2**40)

10 loops, best of 3: 255 ms per loop

Product of two primes:

sage: p = next_prime(10^5)*next_prime(10^6); p

100003300009

sage: %timeit slow_factors(p)

10 loops, best of 3: 473 ms per loop

sage: %timeit factors(p)

10 loops, best of 3: 183 ms per loop

Primes:

sage: p = next_prime(10^10); p

10000000019

sage: %timeit factors(p)

10 loops, best of 3: 96.9 ms per loop

sage: %timeit slow_factors(p)

10 loops, best of 3: 144 ms per loop

When there are lots of factors, then the method I posted gets much faster.

@mike: Thanks for pointing out the error in my code I’ve update the post now. Also the method with the prime factors is clearly much more efficient, thanks

@Ryan: I’ve not come across generators before, thanks for your code looks a hell of a lot neater than what I wrote!

set(reduce(list.__add__, [[i, n/i] for i in range(1, sqrt(n) + 1) if n % i == 0]))

Actually, it can be a generator expression instead of a list comprehension, which is better for memory:

set(reduce(list.__add__, ([i, n/i] for i in range(1, sqrt(n) + 1) if n % i == 0)))

Just a heads-up:

What you’re computing here are divisors, not factors. Factors of n are the list of prime numbers that multiply together to give n. For example, the factors of 135 would be [3, 3, 3, 5]. 3x3x3x5=135

Divisors of n, on the other hand, are all the numbers that divide evenly into n. So, the divisors of 135 are [1, 3, 5, 9, 15, 27, 45, 135].

Jon-Erik is partially correct.

Factors are either composite numbers or prime numbers. A divisor is not necessarily a factor. In the expression 100/3, 3 is the divisor, but it is not a factor of 100.

2, 4, and 5, 10, 20, and 25, are all factors of 100.

The prime factorization of 100 is (where the character ^ refers to raising to a power):

100 = 2^2 * 5^2

If you have the prime numbers, then you can generate all other factors by partitioning the set of prime numbers in various ways, although all the partitions won’t necessarily generate a unique set of factors if the number has factors that are prime numbers raised to powers.

You’re checking for numbers that aren’t possible. When you factor n, and n%2 ==0, then the highest possible factor is now sqrt(n/2). I’ve modified the code below:

def factors(n):

# calculate the square root of n and use this as the

# limit when checking if a number is divisible as

# factors above sqrt(n) will already be calculated as

# the inverse of a lower factor IE. finding factors of

# 100 only need go up to 10 (sqrt(100)=10) as factors

# such as 25 can be found when 5 is found to be a

# factor 100/5=25

fact=[1,n]

check=2

highest=n

root=sqrt(highest)

while check<root:

if highest%check==0:

fact.append(check)

fact.append(n/check)

highest=highest/check

root = sqrt(highest)

check+=1

# this line checks the sqrt of the number to see if

# it is a factor putting it here prevents it appearing

# twice in the above while loop and putting it outside

# the loop should save some time.

if rootn==check:

fact.append(check)

# return an array of factors sorted into numerial order.

fact.sort()

return fact