CODEWITHSUNDEEP
pythonpython-3.x
nubz0r
nubz0r

Reputation: 75

python: list of all factors that calculate a natural number

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

Upvotes: 1

Views: 1416

Answers (3)

CodeManX
CodeManX

Reputation: 11855

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

Upvotes: 1

Adam Smith
Adam Smith

Reputation: 54163

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.

Upvotes: 3

savanto
savanto

Reputation: 4550

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)

Upvotes: 3

Related Questions