Question

Given a positive integer, write a function that computes the prime factors that can be multplied together to get back the same integer.

Answer 1

Answer:

For finding all prime factors of a given number X is the same as to find the set of the smallest numbers (that are larger than 1) that we can divide X into.

In that case we can  start by finding the smallest number n that divides X.

This is the first prime factor of X.

We can then find the rest of the prime factors by finding the prime factors of X/n

So, we can code it as below:

def primeFactorization(X):

   possible = [2] + range(3,int(ceil(sqrt(X)))+1,2)

   for p in possible:

       if X % p == 0:

           return [p] + primeFactorization(X/p)

   return [X]

primeFactorization(3*3*7*5*11*13*31)

> [3,3,5,7,11,13,31]

Answer 2

Python function that computes the prime factors that can be multplied together to get back the same number.

Program 1 : (Beginners)

import math

x=[]

def PrimeFactorization(number):

  while number%2 == 0:

     x.append(2)

     number/=2

  for i in range(3,int(math.sqrt(number))+1,2):

     while number%i== 0:

       x.append(i)

       number/=i

  if number>2:

      x.append(number)

PrimeFactorization(int(input("Enter the number : ")))

for i in range(0,len(x)):

   if i==len(x)-1:

       print(x[i])

   else:

       print(x[i],end=" x ")

Program 2 :

import math

listoffactors=[]

def PrimeFactorization(n):

   for i in x:

       if n%i==0:

           return [i] + PrimeFactorization(int(n/i))

   return[n]

n=int(input("Enter a number : "))

#Preparing a list of possible factors, 2+odds

x=[2]+list(range(3,math.ceil(math.sqrt(n))+1,2))

PrimeFactorization(n)

Input :

Enter a number : 36

Output :

For 1st program : 2 x 2 x 3 x 3

For second program : [3,3,2,2,1]

Check :

Multiplication of the output list of factor values give 36 back. So, the program written is perfect.

Explanation :

In first program, we first divide number by 2 till it gets odd and store a 2 on each such computation. If the number become odd, then the list we have created comprising of odd numbers till the needed range will be helpful in pulling out the factors among them using modulo. Once the number becomes a prime, or 1, it will be printed too. Thus, we will bring out the prime factors of a number.

In second program, We first input the number and then prepare a list of possible factors of the number. Then we pass the number through function and apply modulo on the number passing each element of the list to compute. Once the number becomes a prime or 1, the recursion stops and the complete list prints.

Links which may help you to understand the mathematical process and computations :

• Mathematical process of prime factorization.

        https://brainly.in/question/609553

• Recursion and it's implementation. (In C++)

        https://brainly.in/question/634885

Hope it helps you!