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

```
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](https://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms). For the size of numbers that interest you, the [quadratic sieve](https://en.wikipedia.org/wiki/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))

```