excobra excobra - 5 months ago 10
Python Question

How to print all factorization of an integer in Python 3.5.1

I am new to programming and trying to learn for loop, nested for loop with if statement.

I have written this code to produce all factorisations of an integer

n
:

n=int(input())
for i in range(0,n+1):
for j in range(0,i):
if i*j == n:
print(i,'times',j,'equals',n)
break


now if n=10 it produces the following result:


5 times 2 equals 10

10 times 1 equals 10


The are couple of problems with this one. First is that it ignores the first factorisation i.e.


1 times 10 equals 10


Second problem i want the
i
and
j
to be swapped in result i.e. it should say:


1 times 10 equals 10

2 times 5 equals 10

10 times 1 equals 10


not


1 times 10 equals 10

5 times 2 equals 10

10 times 1 equals 10

Answer
for i in range(0,n+1):
    for j in range(0,i):

Here, j is in the range (0,i), which means, when i is 1, j iterates from 0 to 1, of course their product won't be n when n is 10.

The fix is simple:

for i in range(0,n+1):
    for j in range(0,n+1):

However, the algorithm is pretty slow for big n. You don't have to iterate j and tests if i * j == n, just calculate j with n / i and tests if it's an integer would do well.

Another optimization is: considering that factors are paired, you only needs to iterate i to the square root of n, instead of all the way up to n.

Comments