4
\$\begingroup\$

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

\$\endgroup\$
2
  • 2
    \$\begingroup\$ What range of numbers are you interested in? The best approach for x on the order of \$10^{8}\$ is not the same as the best approach for x on the order of \$10^{80}\$. \$\endgroup\$ May 22, 2019 at 7:20
  • \$\begingroup\$ i may need like 10^40s to 10^60s \$\endgroup\$
    – random_npc
    May 23, 2019 at 9:44

4 Answers 4

6
\$\begingroup\$

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:

enter image description here

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

enter image description here

\$\endgroup\$
16
  • \$\begingroup\$ But doesn't it depend on the workability of the solutions too? The code you provided for the op function doesn't give the right answer for factors of 30 - [30, 30, 30, 30, 30, 30, 30, 30] and Sedsarq's answer only gives two factors - (5, 6), meanwhile both of our answer's give the right solution - [1, 2, 3, 5, 6, 10, 15, 30]. \$\endgroup\$
    – Justin
    May 21, 2019 at 13:59
  • \$\begingroup\$ @Justin Well, it does emulate the behavior in the OP, which just prints the factor instead of saving it in a list. So what you are actually saying is the code provided in the question is not working (which would make it off-topic)? I did not include any code from sedsarq's answer because it is not complete enough, as you say. \$\endgroup\$
    – Graipher
    May 21, 2019 at 14:03
  • \$\begingroup\$ @Justin Nevermind, my op function gave the wrong answer for all numbers, because I saved x and not i... This should not change the runtime, though. \$\endgroup\$
    – Graipher
    May 21, 2019 at 14:06
  • \$\begingroup\$ The code I shared was not intended as a full solution, but simply to clarify the text. My answer just aimed to present an idea to use for improvement (and that idea is also used by the other solutions given here). @Justin \$\endgroup\$
    – Sedsarq
    May 22, 2019 at 6:38
  • \$\begingroup\$ Thanks buddy...I want to make it more concise though...I'm greedy....suppose consider 100......50 is one of its factor....but 50 already contains 2 and 5 so we can say 10 is also a factor...this logic will reduce the runtime much more...but how to implement this?..any ideas? \$\endgroup\$
    – random_npc
    May 22, 2019 at 15:56
3
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ If you are really very concerned about speed, since you only need the sqrt to define a limit, you could use a faster, more approximate sqrt method. As long as it convergences from above the true sqrt, you won't go below the limit (and maybe miss a divisor). \$\endgroup\$ May 22, 2019 at 8:44
  • \$\begingroup\$ The sqrt method is only called once though. There's not a lot of time to save there. @HoboProber \$\endgroup\$
    – Sedsarq
    May 22, 2019 at 10:35
  • \$\begingroup\$ So we need sqrt(n)+1?...won't this contain all the divisors....of course this one reduced my time by half....so far so good...is it possible to reduce further?...like suppose 100...the factor 50 has 2,5 already in it right....so with that we can say 10 is a factor...is it possible to implement such logic in our code? \$\endgroup\$
    – random_npc
    May 22, 2019 at 15:52
3
\$\begingroup\$

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)]
```
\$\endgroup\$
7
  • \$\begingroup\$ This sounds interesting...but suppose if a number can be broken into p^x *q^y...where p and q are primes then number of factors are just permutation of x and y....but how do we permute them? Any ideas? \$\endgroup\$
    – random_npc
    May 22, 2019 at 15:46
  • 1
    \$\begingroup\$ I guess the itertools module can be very useful here. Maybe itertools.product... \$\endgroup\$
    – SylvainD
    May 22, 2019 at 15:49
  • \$\begingroup\$ @Josay You don't even need the permutations, you just need to count how often each prime occurs: quora.com/… \$\endgroup\$
    – Graipher
    May 23, 2019 at 9:51
  • \$\begingroup\$ @Graipher To get the number of factors, this is indeed much easier. You can use nb_divisors from my code in github.com/SylvainDe/ProjectEulerPython/blob/master/prime.py . Getting the different divisors is slightly more complicated \$\endgroup\$
    – SylvainD
    May 23, 2019 at 11:33
  • \$\begingroup\$ @Graipher I've also implemented the generation of the different divisors, you can have a look at my updated answer. \$\endgroup\$
    – SylvainD
    May 23, 2019 at 15:24
1
\$\begingroup\$

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))
\$\endgroup\$
3
  • \$\begingroup\$ Yeah...this is what I wanted...but can u simplify without using heapq...(idk what it does...and I don't want to use unnecessary functions).... I kinda found the code till I get the prime factors and their respective powers and stored them in separate lists...now I just need the code for Cartesian product...ie:permuting the powers of the primes....can u help me? \$\endgroup\$
    – random_npc
    May 24, 2019 at 12:31
  • 1
    \$\begingroup\$ This site is code review, not a code writing service. Supplying improved code is already going above and beyond expectations. \$\endgroup\$ May 24, 2019 at 13:05
  • \$\begingroup\$ lol...agreed...anyways...thanks for informing...i just joined stack overflow recently..my bad \$\endgroup\$
    – random_npc
    May 24, 2019 at 16:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.