Given an integer n. The task is to count the number of operations required to reduce n to 0. In every operation, n can be updated as n = n – d where d is the smallest prime divisor of n.
Examples:
Input: n = 5
Output: 1
5 is the smallest prime divisor, thus it gets subtracted and n gets reduced to 0.
Input: n = 25
Output: 11
5 is the smallest prime divisor, thus it gets subtracted and n gets reduced to 20. Then 2 is the smallest divisor and so on.
Input: n = 4
Output: 2
Approach:
- When n is even then the smallest prime divisor of n will be 2 and subtracting 2 from n will again give an even integer i.e. gain 2 will be chosen as the smallest prime divisor and these steps will repeat until n gets reduced to 0.
- When n is odd then the smallest prime divisor of n will also be odd and subtracting an odd integer from another odd integer will give an even integer as the result and then the result can be found out by repeating step 1 for the current even integer.
- Thus, the task is to find the smallest divisor d, subtract it, n = n – d and print 1 + ((n – d) / 2).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include<bits/stdc++.h>using namespace std;// Function to return the required // number of operationsint countOperations (int n){ int i = 2; // Finding the smallest divisor while ((i * i) < n && (n % i)) i += 1; if ((i * i) > n) i = n; // Return the count of operations return (1 + (n - i)/2);}// Driver codeint main(){ int n = 5; cout << countOperations(n);}//This code is contributed by Shivi_Aggarwal |
Java
// Java implementation of the approachclass GFG{// Function to return the required // number of operationsstatic int countOperations (int n){ int i = 2; // Finding the smallest divisor while ((i * i) < n && (n % i) > 0) i += 1; if ((i * i) > n) i = n; // Return the count of operations return (1 + (n - i) / 2);}// Driver codepublic static void main(String[] args){ int n = 5; System.out.println(countOperations(n));}}// This code is contributed// by Akanksha Rai |
Python3
# Python3 implementation of the approach# Function to return the required # number of operationsdef countOperations(n): i = 2 # Finding the smallest divisor while ((i * i) < n and (n % i)): i += 1 if ((i * i) > n): i = n # Return the count of operations return (1 + (n - i)//2)# Driver coden = 5print(countOperations(n)) |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the required // number of operationsstatic int countOperations (int n){ int i = 2; // Finding the smallest divisor while ((i * i) < n && (n % i) > 0) i += 1; if ((i * i) > n) i = n; // Return the count of operations return (1 + (n - i) / 2);}// Driver codestatic void Main(){ int n = 5; Console.WriteLine(countOperations(n));}}// This code is contributed by mits |
PHP
<?php// PHP implementation of the approach // Function to return the required // number of operations function countOperations($n){ $i = 2; # Finding the smallest divisor while (($i * $i) < $n and ($n % $i)) $i += 1; if (($i * $i) > $n) $i = $n; # Return the count of operations return 1 + floor(($n - $i) / 2);}// Driver code $n = 5 ;echo countOperations($n); // This code is contributed by Ryuga?> |
Javascript
<script>// JavaScript implementation of the approach// Function to return the required // number of operationsfunction countOperations (n){ var i = 2; // Finding the smallest divisor while ((i * i) < n && (n % i)) i += 1; if ((i * i) > n) i = n; // Return the count of operations return (1 + (n - i)/2);}// Driver codevar n = 5;document.write( countOperations(n))</script> |
Output:
1
Time Complexity: 
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
