pythonwhile-loopfactorization

While loop doesn't stop when number is power of 2


I have some issues in python console app. I coded an factorization console app. It works well, but when I input a number that is power of 2 like 4, 8, 16, the while loop doesn't stop. So it doesn't print anything and the code doesn't stop. Bellow is my code.

import math

n=input("Input check number:")
n=int(n)
sent= str(n) + "=1"

for m in range(2, int(n / 2)+1):
    if n % m == 0:
        k = n
        i = 0
        while k % m == 0:
            k = k / m
            i += 1
        sent = sent + "*" + str(m) + "^" + str(i)

if sent == str(n)+ "=1":
    sent = sent + "*" + str(n)

print(sent)

I want someone to help me. Thank you in advance.


Solution

  • The problem is that you don't change n or m inside the while loop. So, for example, for input n=4, m=2, k comes out to be n/m=2 which satisfies k%m==0 and since neither n nor m changes so it runs forever.

    You can simplify the code by modifying n in the while loop to keep decreasing if it is divisible by the current divisor m. You can't do the same for k since k is reset to n again with the line k = n and it will start with the original number giving incorrect output.

    Here is a bit modified version of the code with the outer while loop:

    n=input("Input check number:")
    n = int(n)
    sent = str(n) + "=1"
    
    m = 2  # start division with 2
    while n > 1: # keep dividing till the number is greater than 1
        if m > n:
            break
        i = 0
        while n % m == 0:
            n = n / m   # modify n by dividing it with current divisor
            i += 1
        
        if i > 0: # add only if m divides n at least once
            sent = sent + "*" + str(m) + "^" + str(i)
    
        m = m + 1
    
    if sent == str(n)+ "=1":
        sent = sent + "*" + str(n)
    
    print(sent)
    

    Output (for input 18):

    18=1*2^1*3^2