Find all the factors of a given number

Question

The most basic code(i guess so) to find all the factors of a number

Note:factors include 1 and the number itself

Here's the code:

c=0
x=int(input("Enter number:"))
for i in range(1,x+1):
    if x%i==0:
        print("factor",c+1,":",i)
        c=c+1
print("Total number of factors:",c)

Please make this code efficient.....ie: Help to reduce the number of iterations

Answer 1

Just to have a more readable (than the answer by @Justin) and complete (than the answer by @Sedsarq) version of the algorithm presented in the other answers, here is a version that keeps the factors in a set and uses the fact that factors always come in pairs:

from math import sqrt

def get_factors(n):
    """Returns a sorted list of all unique factors of `n`."""
    factors = set()
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            factors.update([i, n // i])
    return sorted(factors)

Compared to your code this has the added advantage that it is encapsulated in a function, so you can call it repeatedly and give it a clear name and docstring describing what the function does.

It also follows Python's official style-guide, PEP8, which programmers are encouraged to follow.

With regards to which code is fastest, I'll let this graph speak for itself:

For the op function I used this code which has your checking of all factors up to x:

def op(x):
    factors = []
    for i in range(1,x+1):
        if x%i==0:
            factors.append(i)
    return factors

And the factors function is from the answer by @Justin.

---

If all you really want is the number of factors, the best way is probably to use the prime factor decomposition. For this you can use a list of primes together with the algorithm in the answer by @Josay:

from math import sqrt
from functools import reduce
from operators import mul

def prime_sieve(limit):
    prime = [True] * limit
    prime[0] = prime[1] = False

    for i, is_prime in enumerate(prime):
        if is_prime:
            yield i
            for n in range(i * i, limit, i):
                prime[n] = False

def prime_factors(n):
    primes = prime_sieve(int(sqrt(n) + 1))
    for p in primes:
        c = 0
        while n % p == 0:
            n //= p
            c += 1
        if c > 0:
            yield p, c
    if n > 1:
        yield n, 1

def prod(x):
    return reduce(mul, x)

def number_of_factors(n)
    return prod(c + 1 for _, c in prime_factors(n))

Comparing this with just taking the len of the output of the get_factors function and this function which implements your algorithm as op_count:

def len_get_factors(n):
    return len(get_factors(n))

def op_count(n):
    c = 0
    for i in range(1, n + 1):
        if n % i == 0:
            c = c + 1
    return c

The following timings result (note the increased range compared to the previous plot):

Answer 2

All answers provided are great and offer suggestions with a complexity in O(sqrt(n)) instead of the original O(n) by using the trick to stop at sqrt(n).

On big inputs, we can go for an even faster solution by using the decomposition in prime numbers:

• the decomposition in prime numbers can be computed in a time proportional to the square root of the biggest prime divisor if its multiplicity is one (the actually complexity is actually a bit more tricky than this)

• the decomposition can be reused to generate all possible divisors (for each prime p with multiplicity n, you take p ^ m with 0 <= m <= n.

I can provide the following piece of code for the first task but I do not have a snippet for the second task (yet?)

def prime_factors(n):
    """Yields prime factors of a positive number."""
    assert n > 0
    d = 2
    while d * d <= n:
        while n % d == 0:
            n //= d
            yield d
        d += 1
    if n > 1:  # to avoid 1 as a factor
        assert d <= n
yield n

Edit: I tried to implement the second step and got something which is not highly tested but seems to work:

def mult(iterable, start=1):
    """Returns the product of an iterable - like the sum builtin."""
    return functools.reduce(operator.mul, iterable, start)


def yield_divisors(n):
    """Yields distinct divisors of n."""
    elements = [[p**power for power in range(c + 1)] for p, c in collections.Counter(prime_factors(n)).items()]
    return [mult(it) for it in itertools.product(*elements)]
```

Answer 3

Divisors come in pairs. Since 2*50 = 100, both 2 and 50 are divisors to 100. You don't need to search for both of these, because once you've found that 100 is divisible by 2, you can do 100 / 2 to find 50, which is the other divisor. So for every divisor you find, use division to find its "partner" at the same time. That way you don't need to look further than the square root of x:

for i in range(1, int(math.sqrt(x)) + 1):
    if x % i == 0:
        divisor1 = i
        divisor2 = x // i

Answer 4

Since you say in a comment that you may need to find the divisors of a number \$n\$ up to \$10^{60}\$, trial division is not practical, even if performed only up to \$\sqrt n\$ . The only option is to find the prime factorisation and then reconstruct the divisors from the prime factorisation.

There are quite a few algorithms to find the prime factorisation. For the size of numbers that interest you, the quadratic sieve is probably the best option.

Given the prime factorisation, reconstruction of the divisors is just a matter of taking some Cartesian products. Generating them in order is slightly trickier: I reproduce here some code which I wrote for an earlier answer to a similar question. It assumes that primeFactors gives output in the form [(prime, power) ...] in ascending order of primes.

import heapq

def divisors(n):
    primes = [(1, 1)] + list(primeFactors(n))
    q = [(1, 0, 1)]
    while len(q) > 0:
        # d is the divisor
        # i is the index of its largest "prime" in primes
        # a is the exponent of that "prime"
        (d, i, a) = heapq.heappop(q)
        yield d
        if a < primes[i][1]:
            heapq.heappush(q, (d * primes[i][0], i, a + 1))
        if i + 1 < len(primes):
            heapq.heappush(q, (d * primes[i + 1][0], i + 1, 1))
            # The condition i > 0 is to avoid duplicates arising because
            # d == d // primes[0][0]
            if i > 0 and a == 1:
                heapq.heappush(q, (d // primes[i][0] * primes[i + 1][0], i + 1, 1))