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

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

```