Minimum operations to reduce N to a prime number by subtracting with its highest divisor - Coding

Given a positive integer N. In one operation subtract N with its highest divisor other than N and 1. The task is to find minimum operations required to reduce N exactly to a prime number.

Examples:

Input: N = 38
Output: 1
Explanation: Highest divisor of 38 is 19, so subtract it (38 – 19) = 19. 19 is a prime number.
So, number of operations required = 1.

Input: N = 69
Output: 2

Approach: This problem can be solved by using simple concepts of maths. Follow the steps below to solve the given problem.

At first, check whether N is already prime or not.
- If N is already a prime, return 0.
- Else, Initialize a variable say count = 0 to store the number of operations required.
- Initialize a variable say i=2 and run a while loop till N!=i
  - Run while loop and on each iteration subtract current value of N with its largest divisor.
  - Compute the steps and increment the count by 1.
- Return the count.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function check whether a number
// is prime or not
bool isPrime(int n)
{
    // Corner case
    if (n <= 1)
        return false;
 
    // Check from 2 to square root of n
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
 
    return true;
}
 
// Function to minimum operations required
// to reduce the number to a prime number
int minOperation(int N)
{
    // Because 1 cannot be converted to prime
    if (N == 1)
        return -1;
 
    // If given number is already prime
    // return 0
    if (isPrime(N) == true) {
        return 0;
    }
 
    // If number is not prime
    else {
        // Variable for total count
        int count = 0;
        int i = 2;
 
        // If number is not equal to i
        while (N != i) {
            // If N is completely divisible by i
            while (N % i == 0) {
                // Temporary variable to store
                // current number
                int temp = N;
 
                // Update the number by decrementing
                // with highest divisor
                N -= (temp / i);
 
                // Increment count by 1
                count++;
                if (isPrime(N))
                    return count;
            }
            i++;
        }
 
        // Return the count
        return count;
    }
}
 
// Driver Code
int main()
{
    int N = 38;
 
    cout << minOperation(N);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.Arrays;
 
class GFG {
    // Function check whether a number
    // is prime or not
    public static boolean isPrime(int n) {
        // Corner case
        if (n <= 1)
            return false;
 
        // Check from 2 to square root of n
        for (int i = 2; i <= Math.sqrt(n); i++)
            if (n % i == 0)
                return false;
 
        return true;
    }
 
    // Function to minimum operations required
    // to reduce the number to a prime number
    public static int minOperation(int N) {
        // Because 1 cannot be converted to prime
        if (N == 1)
            return -1;
 
        // If given number is already prime
        // return 0
        if (isPrime(N) == true) {
            return 0;
        }
 
        // If number is not prime
        else {
            // Variable for total count
            int count = 0;
            int i = 2;
 
            // If number is not equal to i
            while (N != i) {
                // If N is completely divisible by i
                while (N % i == 0) {
                    // Temporary variable to store
                    // current number
                    int temp = N;
 
                    // Update the number by decrementing
                    // with highest divisor
                    N -= (temp / i);
 
                    // Increment count by 1
                    count++;
                    if (isPrime(N))
                        return count;
                }
                i++;
            }
 
            // Return the count
            return count;
        }
    }
 
    // Driver Code
    public static void main(String args[]) {
        int N = 38;
 
        System.out.println(minOperation(N));
    }
}
 
// This code is contributed by gfgking.

Python3

# python program for the above approach
import math
 
# Function check whether a number
# is prime or not
def isPrime(n):
 
    # Corner case
    if (n <= 1):
        return False
 
    # Check from 2 to square root of n
    for i in range(2, int(math.sqrt(n)) + 1):
        if (n % i == 0):
            return False
 
    return True
 
# Function to minimum operations required
# to reduce the number to a prime number
def minOperation(N):
 
    # Because 1 cannot be converted to prime
    if (N == 1):
        return -1
 
    # If given number is already prime
    # return 0
    if (isPrime(N) == True):
        return 0
 
    # If number is not prime
    else:
        # Variable for total count
        count = 0
        i = 2
 
        # If number is not equal to i
        while (N != i):
           
            # If N is completely divisible by i
            while (N % i == 0):
               
                # Temporary variable to store
                # current number
                temp = N
 
                # Update the number by decrementing
                # with highest divisor
                N -= (temp // i)
 
                # Increment count by 1
                count += 1
                if (isPrime(N)):
                    return count
            i += 1
 
        # Return the count
        return count
 
# Driver Code
if __name__ == "__main__":
    N = 38
    print(minOperation(N))
 
# This code is contributed by rakeshsahni

C#

// C# program for the above approach
using System;
 
public class GFG {
     
    // Function check whether a number
    // is prime or not
    public static bool isPrime(int n)
    {
       
        // Corner case
        if (n <= 1)
            return false;
 
        // Check from 2 to square root of n
        for (int i = 2; i <= Math.Sqrt(n); i++)
            if (n % i == 0)
                return false;
 
        return true;
    }
 
    // Function to minimum operations required
    // to reduce the number to a prime number
    public static int minOperation(int N) {
        // Because 1 cannot be converted to prime
        if (N == 1)
            return -1;
 
        // If given number is already prime
        // return 0
        if (isPrime(N) == true) {
            return 0;
        }
 
        // If number is not prime
        else {
            // Variable for total count
            int count = 0;
            int i = 2;
 
            // If number is not equal to i
            while (N != i) {
                 
                // If N is completely divisible by i
                while (N % i == 0) {
                     
                    // Temporary variable to store
                    // current number
                    int temp = N;
 
                    // Update the number by decrementing
                    // with highest divisor
                    N -= (temp / i);
 
                    // Increment count by 1
                    count++;
                     
                    if (isPrime(N))
                        return count;
                }
                i++;
            }
 
            // Return the count
            return count;
        }
    }
 
    // Driver Code
    public static void Main(string []args) {
        int N = 38;
 
        Console.WriteLine(minOperation(N));
    }
}
 
// This code is contributed by AnkThon

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function check whether a number
    // is prime or not
    const isPrime = (n) => {
        // Corner case
        if (n <= 1)
            return false;
 
        // Check from 2 to square root of n
        for (let i = 2; i <= parseInt(Math.sqrt(n)); i++)
            if (n % i == 0)
                return false;
 
        return true;
    }
 
    // Function to minimum operations required
    // to reduce the number to a prime number
    const minOperation = (N) => {
     
        // Because 1 cannot be converted to prime
        if (N == 1)
            return -1;
 
        // If given number is already prime
        // return 0
        if (isPrime(N) == true) {
            return 0;
        }
 
        // If number is not prime
        else
        {
         
            // Variable for total count
            let count = 0;
            let i = 2;
 
            // If number is not equal to i
            while (N != i) 
            {
             
                // If N is completely divisible by i
                while (N % i == 0)
                {
                 
                    // Temporary variable to store
                    // current number
                    let temp = N;
 
                    // Update the number by decrementing
                    // with highest divisor
                    N -= parseInt(temp / i);
 
                    // Increment count by 1
                    count++;
                    if (isPrime(N))
                        return count;
                }
                i++;
            }
 
            // Return the count
            return count;
        }
    }
 
    // Driver Code
    let N = 38;
    document.write(minOperation(N));
 
    // This code is contributed by rakeshsahni
 
</script>

Output

Time Complexity: O(sqrtN)

Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Mathematical

Related
Check if A and B can be reduced to 0 by decrementing with x and y with absolute difference at most K
Find minimum value expression by inserting addition or multiplication operator between digits of given number
Check if a number can be represented as sum of two positive perfect biquadrates
Program to Subtract two integers of given base
Generate N Random Hexadecimal Numbers

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	10