Question

Clint and his love for numbers
Clint loves numbers so much, that he tries to find some quirky math tricks whenever he can One day,
he decides to take up a number and tries to find out in how many minimum numbers of steps, can he
reduce that number to 0. The steps he performs were
1. Either decrease the number by 1, or
2. Replace the number by its largest prime divisor (note that divisor cannot be 1 and number itself).
Help Clint find the minimum number of steps to reduce the given norber to 0
Input Specification
input1: The number N
Output Specification
Return the minimum number of steps to reduce the number to 0.
Example 1
input1:9
Output: 4
Explanation:
Here, 9 can be reduced to 0 as
1 Replace it by its largest prime divisorie 3
2 Reduce 3 to 2​

Answer 1

Answer:

import math

def is_prime(num):

   for val in range(2, int(math.sqrt(num)) + 1):

       if num % val == 0:

           return False

   return True

def largest_prime(num):

   maxp = 0

   n = int(math.sqrt(num)) + 1

   for val in range(2, n):

       if num % val == 0:

           if is_prime(val):

               maxp = max(maxp, val)

           if is_prime(num // val):

               maxp = max(maxp, num // val)

   if not maxp:

       return num

   return maxp

number = int(input())

l = largest_prime(number)

if l == number:

   count = 0

else:

   count = 1

number = l

while number > 0:

   while is_prime(number):

       number -= 1

       count += 1

       if number == 0:

           print(count)

           break

   number = largest_prime(number)

   count += 1

Explanation:

Calculating factors and if its prime then reducing by 1 else replacing it with the largest prime divisor and incrementing counter likewise.