How to find factors of a number using the simplest python method

Question

how to find all factors of a number and list the factors in a list.

Input:

   >>>factors(72)

Output:

   [2, 2, 2, 3, 3]

I have taken some code down because this is getting a lot of views and this is a HW questions so i don't want it copied.

For reading material, please see [this post](http://stackoverflow.com/questions/453793/which-is-the-fastest-algorithm-to-find-prime-numbers) discussing various fast algorithms to determine prime factorization. It is tagged as `C++` but is mostly language agnostic. — Cory Kramer, Aug 13 '14 at 18:16
No, you don't need `math`. Because you use `yield`, it returns a generator. Try `list(factors(360))` (or whatever number you want) for output — hlt, Aug 13 '14 at 18:17
Also, you should take the second `for` loop outside of the `def` block (or you'll get some nasty recursion problems). — hlt, Aug 13 '14 at 18:21
if i do that it give me more issues: for i in range(2, n + 1): TypeError: 'float' object cannot be interpreted as an integer — Michelle, Aug 13 '14 at 18:27

score 1 · Answer 1 · edited Apr 13 '17 at 12:19

With regard to your question 1: factoring is hard. That's why it's at the core of many cryptographic algorithms --- we currently don't know a way to quickly factor a very large number.

For small numbers, your algorithm will do. For slightly larger numbers, I've had the same question --- apparently Pollard's Rho is a good algorithm for this purpose. For large numbers, we don't know.

Now to your question 2:

First of all, in your prime(n) function, you don't need to check if n%i==0 all the way up to n. You only need to check this up to sqrt(n), because if there is any pair of integers (a,b) such that a * b = n, then one of these integers will necessarily be less than or equal to sqrt(n). So you only need to check up to sqrt(n). This saves you a lot of computations.

Here's your factors function:

from math import ceil

def factors(n):
        factors = []
        while n > 1:
                for i in range(2,int((ceil(n/2.0))+1)):
                        if n%i==0:
                                factors.append(i)
                                n = n/i
                                continue
                factors.append(n)
                break
        return factors

score 1 · Accepted Answer · answered Aug 13 '14 at 18:29

1

def factors(n):
a = []
x = 2
while x * x <= n :
    if n % x == 0:          
        a.append(x)
        n /= x
    else: x += 1
if n > 1: a.append(n)
return a

all downvoted as quickly as possible.

answered Aug 13 '14 at 18:29

Pierre Thibault · Answer 3 · 2018-08-05T03:22:56.517

Here is a solution using decomposition by prime numbers. It is much faster.

import bisect
import math
import pathlib


primes = []
last_prime = None


def _get_primes():
    """
    Load all the primes in global primes. Set global last_prime to last prime
    read.
    """

    global primes
    global last_prime
    path_to_primes = pathlib.Path(__file__).parent \
            .joinpath('../resources/primes.txt')
    with path_to_primes.open() as file:
        for line in file:
            for n in line.split():
                n = n.strip()
                if n:
                    n = int(n)
                    primes.append(n)
    last_prime = primes[-1]


def gen_primes_before(n):
    """
    Generates all the primes before n in reverse order.
    """

    assert n <= last_prime, "Maximum value for n is {}".format(last_prime)
    pos = bisect.bisect_left(primes, n)
    if pos:
        yield from primes[:pos]


def gen_factors(n):
    """
    Generates all the factors of a number. May return some values multiple
    times. Values returned are not ordered.
    """
    type_n = type(n)
    assert type_n is int or (type_n is float and n.is_integer()), "Wrong type"
    n = int(n)
    r = int(math.sqrt(n)) + 1
    assert r <= last_prime, "n is over limit"
    yield 1
    yield n
    for prime in gen_primes_before(r):
        partner = n/prime
        if partner.is_integer():
            yield from gen_factors(prime)
            yield from gen_factors(partner)


def get_factors(n):
    """
    Get all the factors of n as a sorted list.
    """
    return sorted(set(gen_factors(n)))


_get_primes()
if __name__ == '__main__':
    l = (1e9,)
    for n in l:
        print("The factors of {} are {}".format(n, get_factors(n)))

I made a repository: https://github.com/Pierre-Thibault/Factor

How to find factors of a number using the simplest python method

3 Answers3