excobra - 1 year ago 47

Python Question

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`

`j`

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`

.

Source (Stackoverflow)