python: list of all factors that calculate a natural number

Question

I'm new in python and I'm trying to figure out how to write a function in python that gives me back a list of all factors that calculate a natural number. The number entered shouldn't come on the result list.

it should look like this:

realfactor(250)
[1, 2, 5, 10, 25, 50, 125]

I probably should start like this:

def realfactor(n):
factorlist = []

I would appreciate the help

I think the word is divisor. Find all divisors of a natural number. — David Mahone, Apr 26 '14 at 22:48

score 3 · Answer 1 · answered Apr 26 '14 at 22:45

3

A simple iteration through all possible factors to build the list of viable ones:

def realfactor(n):
    factorlist = []
    for i in range(1, n//2 + 1): # check all 1 <= i <= 1/2 of n
        if n % i == 0:           # i is a factor of n
            factorlist.append(i)

    print(factorlist)

answered Apr 26 '14 at 22:45

savanto

4,470
23
40

2

This is O(n). Can be improved to O(sqrt(n)) by only checking numbers not larger than sqrt(n) – David Mahone Apr 26 '14 at 22:47
@DavidMahone O( sqrt(n) ) IS O(n). Big "O" notation is restricted to orders of magnitude. Regardless, doing `for i in range(1, floor(sqrt(n))+2)` for 6 returns `1, 2` but not `3`. – Adam Smith Apr 26 '14 at 22:59
1

@AdamSmith No, `O(√n) < O(n)`. – Veedrac Apr 26 '14 at 23:01
It's `sqrt(250) + 1`, or `int(250**0.5) + 1`. See the [second solution in my answer](http://stackoverflow.com/a/23317320/2044940). – CodeManX Apr 26 '14 at 23:05

score 3 · Answer 2 · answered Apr 26 '14 at 23:08

3

def realfactor(n):
    factors = [1]
    for i in range(2, math.floor( math.sqrt(n) )+1 ):
        if n % i == 0:
            factors.append(i)
            factors.append(i/n)
    return sorted(factors)

For very large n, this will be slightly faster than savanto's answer.

answered Apr 26 '14 at 23:08

Adam Smith

52,157
12
73
112

You can avoid the math module import if you use the build-in `**` operator (pow). If the order of factors doesn't matter, you can leave out `sorted()` for better performance. `i/n` should be `i//n` (int division), or you'll get floats and worse speed. – CodeManX Apr 26 '14 at 23:15
@CoDEmanX if `n % 1 == 0`, `i/n` equals `i//n`. I have to import `math` anyway for `math.floor`, so doing the less-readable `n**0.5` isn't as good. You're right about `sorted` but since OP's example had it sorted I'm assuming it's a requirement until noted otherwise. – Adam Smith Apr 27 '14 at 02:16
@CoDEmanX I suppose I could do `int()` instead of `math.floor()` but I'm fairly against doing that in general. Negative numbers behave poorly, and though that's not an issue here I find it hard to believe this is actually a performance bottleneck. – Adam Smith Apr 27 '14 at 02:19
Negative numbers? sqrt isn't defined for neg. numbers, how would u get 1 here? Even if, `int()` gives 0 for values >-1.0 and <1.0. `sqrt()` and `**0.5` are equal, except the import. But no, there's no bottleneck. In fact, int() + **0.5 are sometimes faster, but also sometimes a bit slower than the math functions. The differences are very little, so they might perform equally - taking some timing epsilon into account. `i/n` is not the same as `i//n` - the former is a true division, the other an int division. The latter is faster and gives int instantly, whereas a truediv always returns a float. – CodeManX Apr 27 '14 at 03:50
@CoDEmanX Which is all premature optimization AT BEST. Regardless my point was that `int` as substitute for `math.floor` behaves poorly with negative numbers so I don't use them interchangeably. `x/y` and `x//y` are equivalently fast on my CPython implementation. I know the difference between integer division and true division. – Adam Smith Apr 27 '14 at 03:56
@CoDEmanX write code that's easy to read, not code that's fast. `math.floor` is easier to read than `~~` or `int`. `math.sqrt` is easier to read than `x ** 0.5`. – Adam Smith Apr 27 '14 at 03:59
`int(x/y)` is 3-9x slower than `x//y` on my machine, also CPython. Just `x/y` is as fast as the int division or even a bit faster. But for `range()` we need int, so... Nice negative number handling with `int()` is possible, but sure, there's no reason to do it. I'm all for readable code, and `math.floor` / `math.sqrt` don't slow anything down - so use them! – CodeManX Apr 27 '14 at 04:30

score 1 · Answer 3 · edited May 23 '17 at 11:49

1. Solution taken from this post and added import for python 3.x:

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)))

factors(250)
#~ {1, 2, 5, 10, 50, 25, 250, 125}

Horrible to read!

2. If you don't care about the order, here is a fast one:

def factors(n):
    return [val for sublist in [
            (i, n//i) for i in range(1, int(n**0.5) + 1) if n % i == 0
        ] for val in sublist
    ]

print(factors(250))
#~ [1, 250, 2, 125, 5, 50, 10, 25]

3. Not as efficient, but more readable and pythonic:

def factors(n):
    fac_up = []
    fac_down = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            fac_up.append(i)
            fac_down.append(n//i)

    fac_up.extend(reversed(fac_down))
    return fac_up

print(factors(250))
#~ [1, 2, 5, 10, 25, 50, 125, 250]

Comparison

from timeit import timeit

n = 250

# sorted
def factors_a(n=n):
    factorlist = []
    for i in range(1, n//2 + 1): # check all 1 <= i <= 1/2 of n
        if n % i == 0:           # i is a factor of n
            factorlist.append(i)

    return factorlist

# partially sorted ?!
def factors_b(n=n):    
    from functools import reduce
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

# unsorted
def factors_c(n=n):
    return [val for sublist in [
            (i, n//i) for i in range(1, int(n**0.5) + 1) if n % i == 0
        ] for val in sublist
    ]

# unsorted
def factors_d(n=n):
    factorlist = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            factorlist.extend((i, n//i))
    return factorlist

# sorted
def factors_e(n=n):
    fac_up = []
    fac_down = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            fac_up.append(i)
            fac_down.append(n//i)

    fac_up.extend(reversed(fac_down))
    return fac_up

# sorted
def factors_f(n=n):
    import math
    factors = [1]
    for i in range(2, math.floor( math.sqrt(n) )+1 ):
        if n % i == 0:
            factors.append(i)
            factors.append(i/n)
    return sorted(factors)


def test():
    global n
    for i in [12, 250, 10000, 99887766554433221100]:
        print("--- TEST RUN, n = %i ---" % i)
        n = i
        for func in (factors_a, factors_b, factors_c, factors_d, factors_e, factors_f):
            print(func.__name__, timeit(func, number=50000))
    print("--- DONE ---")

test()

Timing

--- TEST RUN, n = 12 ---
factors_a 3.6315924063687817
factors_b 2.066486179519643
factors_c 1.1868003486015368
factors_d 0.9670367921808065
factors_e 1.3348606748124894
factors_f 1.7466818274729121
--- TEST RUN, n = 250 ---
factors_a 3.873070439592084
factors_b 2.060870580367009
factors_c 1.1865506143719813
factors_d 0.9752904229490014
factors_e 1.3438553833548212
factors_f 1.752019469006882
--- TEST RUN, n = 10000 ---
factors_a 3.5701808777132555
factors_b 2.0908904308173533
factors_c 1.2107483217776007
factors_d 0.9822444949425062
factors_e 1.3818273874635452
factors_f 1.75292261745426
--- TEST RUN, n = 99887766554433221100 ---
factors_a 3.4753276265071236
factors_b 2.066540915789119
factors_c 1.203012119807454
factors_d 0.9725134125242221
factors_e 1.362277986697336
factors_f 1.7789864895491974
--- DONE ---

python: list of all factors that calculate a natural number

3 Answers3