4

What is the easiest way to get a list of whole factor pairs of a given integer?

For example: f(20) would return [(1,20), (2,10), (4,5)].

Adrian Toman
  • 11,316
  • 5
  • 48
  • 62
Christopher O'Donnell
  • 476
  • 1
  • 7
  • 13

3 Answers3

12
def f(value):
    factors = []
    for i in range(1, int(value**0.5)+1):
        if value % i == 0:
            factors.append((i, value / i))
    return factors

Or the same thing using a list comprehension:

def f(val):
    return [(i, val / i) for i in range(1, int(val**0.5)+1) if val % i == 0]
Steve Mayne
  • 22,285
  • 4
  • 49
  • 49
  • I added the hardcoded factor of 1 to micro optimise the function (as there's little point doing % 1) - but what do people think about this? Does the messiness of the code and the inability to accept values of less than 1 outweigh the exceptionally minor optimisation? – Steve Mayne Mar 31 '11 at 21:00
  • It's a bit problematic as it returns 1 as a factor of 0, which is "incorrect". That could be fixed by doing `result = [(1, value)] * (value > 0)` which is possibly still faster than doing an extra iteration. – Benjamin Apr 01 '11 at 17:10
3

Or this:

def f(n):
        factors_list = []
        for i in xrange(1, int(n**0.5) + 1):
            if n % i == 0:
                factors_list.append((i, n/i))
        return factors_list

print f(20)

EDIT: Or in a one-liner using list comprehension:

def f(n):
    return [(i, n / i) for i in xrange(1, int(n**0.5) + 1) if n % i == 0]

print f(36)

EDIT2: If you want the function to work for negative integers (as well as 0 and positive integers) use:

def f(n):
    return [(i, n / i) for i in xrange(1, int(math.sqrt(math.fabs(n))) + 1) if n % i == 0]

print f(-36)
Benjamin
  • 11,560
  • 13
  • 70
  • 119
0

How about this:

def f(n):
    from itertools import takewhile
    if not isinstance(n,int):
          raise ValueError("supplied %s type, requires integer input" %(type(n).__name__))
    return [(i,n/i) for i in takewhile(lambda x:x*x<n,xrange(1,n)) if (n%i)==0]
highBandWidth
  • 16,751
  • 20
  • 84
  • 131
  • There's so much wrong to unfortunate with the second line... (1) `assert` is for sanity checks, not for input validation. (2) Explicit typechecking is usually a bad idea anyway. (3) But if you do it, at least use `isinstance` (which considers inheritance). (4) Also, if you absolutely have to check if the type is exactly `T`, better use `type(...) is T` - `is` is more appropriate for singletons (a type is essentially one) and `==` *could* have a broken overload. –  Mar 31 '11 at 19:12
  • Any reason why you do (n/i)*i==n, rather than use mod (%)? – Steve Mayne Mar 31 '11 at 19:13
  • @Benjamin: Not with integer division, which truncates. Although in Python 3 you're right because they changed `/` to always return a float. –  Mar 31 '11 at 19:16
  • @Benjamin: try typing `(5/2)*2 == 5` in your python console if you are using Python 2.x – JoshAdel Mar 31 '11 at 19:20
  • Not to criticize excessively, but something along the lines of `raise ValueError("Can only factor integer, not '{}'".format(type(n).__name__))` would be *really* good imho. Perhaps I've spent too much time with the FP guys, but a number crunching function shouldn't output anything imho. –  Mar 31 '11 at 19:20
  • 1
    Checking types is silly, but if you must do it don't just print a message and try to muddle through. Raise a TypeError. But seriously, don't check the parameter types. – Winston Ewert Mar 31 '11 at 19:23
  • 1
    I think your list comprehension is backwards. I also think it's cooler to acknowledge when you see a good answer than to edit it into your own. – Benjamin Mar 31 '11 at 19:45
  • @Benjamin, didn't mean to do that, I was trying to use list comprehension, and thought I needed ceil to do that. The new edit doesn't use that. – highBandWidth Mar 31 '11 at 20:35
  • @highBandWidth: I meant that your answer is now completely different from your original answer. – Benjamin Mar 31 '11 at 20:36
  • The while loop version was better, it was possible to understand. – Winston Ewert Apr 01 '11 at 02:50