Function that prints prime factorization of any number / Python

user_15180760 0
Viewed 1055

I'm looking for help writing a function that takes a positive integer n as input and prints its prime factorization to the screen. The output should gather the factors together into a single string so that the results of a call like prime_factorization(60) would be to print the string “60 = 2 x 2 x 3 x 5” to the screen. The following is what I have so far. UPDATE: I made progress and figured out how to find the prime factorization. However, I still need help printing it the correct way as mentioned above.

""""
Input is a positive integer n
Output is its prime factorization, computed as follows: 

"""
import math
def prime_factorization(n):

    while (n % 2) == 0:
        print(2)
    
        # Turn n into odd number 
        n = n / 2

    for i in range (3, int(math.sqrt(n)) + 1, 2):
    
        while (n % i) == 0:
            print(i)
            n = n / I

    if (n > 2):
        print(n)
    

prime_factorization(60)

Note that I am trying to print it so if the input is 60, the output reads " 60 = 2 x 2 x 3 x 5 "

jupyter jupyter-notebook python-3.x python
3 Answers

You should always separate computation from presentation. You can build the function as a generator that divides the number by increasing divisors (2 and then odds). When you find one that fits, output it and continue with the result of the division. This will only produce prime factors.

Then use that function to obtain the data to print rather than trying to mix in the printing and formatting.

def primeFactors(N):
    p,i = 2,1               # prime divisor and increment
    while p*p<=N:           # no need to go beyond √N 
        while N%p == 0:     # if is integer divisor
            yield p         # output prime divisor
            N //= p         # remove it from the number
        p,i = p+i,2         # advance to next potential divisor 2, 3, 5, ... 
    if N>1: yield N         # remaining value is a prime if not 1

output:

N=60
print(N,end=" = ")
print(*primeFactors(N),sep=" x ")

60 = 2 x 2 x 3 x 5
user_52375600

Use a list to store all factors, then print them together in the required format as a string.

import math
def prime_factorization(n):
    factors = []  # to store factors
    while (n % 2) == 0:
        factors.append(2)
    
        # Turn n into odd number 
        n = n / 2

    for i in range (3, int(math.sqrt(n)) + 1, 2):
    
        while (n % i) == 0:
            factors.append(i)
            n = n / I

    if (n > 2):
        factors.append(n)

    print(" x ".join(str(i) for i in factors))  # to get the required string
    

prime_factorization(60)
user_93507200

Here is a way of doing it with f-strings. In addition, you need to do integer division (with //) to avoid getting floats in your answer.

""""
Input is a positive integer n
Output is its prime factorization, computed as follows:
"""
import math

def prime_factorization(n):
    n_copy = n
    prime_list = []
    while (n % 2) == 0:
        prime_list.append(2)
        # Turn n into odd number
        n = n // 2

    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while (n % i) == 0:
            prime_list.append(i)
            n = n // i

    if (n > 2):
        prime_list.append(n)

    print(f'{n_copy} =', end = ' ')
    for factor in prime_list[:-1]:
        print (f'{factor} x', end=' ' )
    print(prime_list[-1])


prime_factorization(60)
#output: 60 = 2 x 2 x 3 x 5
user_91620000
Related