Given an integer N, the task is to calculate the maximum number of times N can be divided by an integer K, where K is a power of a prime integer and the value of K is always distinct.
Example:
Input: N = 24
Output: 3
Explanation: In the first operation, K = 2 (=21). Hence, the value of N becomes N = 24/2 = 12. In the second operation, K = 3. Hence, N = 12/3 = 4. In the 3rd operation, K = 4 (=22). Hence, N = 4/4 = 1, which can not be further divided. Therefore, {2, 3, 4} is the largest set 3 integers having distinct powers of prime integers than can divide N.Input: N = 100
Output: 2
Approach: The given problem can be solved using a greedy approach. The idea is to divide the number by all of its prime factors in increasing order of their value as well as power. Iterate using a variable i in the range [2, ?N] and if i divides N, then divide N with increasing powers of i (i.e, 1, 2, 3…) until it is divisible with it. Maintain the count of the number of divisions in a variable which is the required answer.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Program to find maximum number of // times N can be divided by distinct // powers of prime integers int maxDivisions( int N) { // Stores the required count int cnt = 0; int range = sqrt (N); // Loop to iterate in range [2, ?N] for ( int i = 2; i <= range; i++) { // If i divides N if (N % i == 0) { int j = i; // Divide N with increasing // powers of i while (N % j == 0 && N) { N = N / j; // Update j j *= i; // Increment cnt cnt++; } // Remove the remaining power // of i to avoid repetition while (N % i == 0) { N /= i; } } } // Return Answer return cnt; } // Driver Code int main() { int N = 100; cout << maxDivisions(N); return 0; } |
Java
// JAVA program of the above approach import java.util.*; class GFG { // Program to find maximum number of // times N can be divided by distinct // powers of prime integers public static int maxDivisions( int N) { // Stores the required count int cnt = 0 ; double range = Math.sqrt(N); // Loop to iterate in range [2, ?N] for ( int i = 2 ; i <= range; i++) { // If i divides N if (N % i == 0 ) { int j = i; // Divide N with increasing // powers of i while (N % j == 0 && N != 0 ) { N = N / j; // Update j j *= i; // Increment cnt cnt++; } // Remove the remaining power // of i to avoid repetition while (N % i == 0 ) { N /= i; } } } // Return Answer return cnt; } // Driver Code public static void main(String[] args) { int N = 100 ; System.out.print(maxDivisions(N)); } } // This code is contributed by Taranpreet |
Python3
# Python code for the above approach from math import ceil, sqrt # Program to find maximum number of # times N can be divided by distinct # powers of prime integers def maxDivisions(N): # Stores the required count cnt = 0 ; _range = ceil(sqrt(N)); # Loop to iterate in range [2, ?N] for i in range ( 2 , _range + 1 ): # If i divides N if (N % i = = 0 ): j = i; # Divide N with increasing # powers of i while (N % j = = 0 and N): N = N / j; # Update j j * = i; # Increment cnt cnt + = 1 # Remove the remaining power # of i to avoid repetition while (N % i = = 0 ): N / = i; # Return Answer return cnt; # Driver Code N = 100 ; print (maxDivisions(N)); # This code is contributed by gfgking |
C#
// C# program to implement // the above approach using System; class GFG { // Program to find maximum number of // times N can be divided by distinct // powers of prime integers public static int maxDivisions( int N) { // Stores the required count int cnt = 0; double range = Math.Sqrt(N); // Loop to iterate in range [2, ?N] for ( int i = 2; i <= range; i++) { // If i divides N if (N % i == 0) { int j = i; // Divide N with increasing // powers of i while (N % j == 0 && N != 0) { N = N / j; // Update j j *= i; // Increment cnt cnt++; } // Remove the remaining power // of i to avoid repetition while (N % i == 0) { N /= i; } } } // Return Answer return cnt; } // Driver Code public static void Main() { int N = 100; Console.Write(maxDivisions(N)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for the above approach // Program to find maximum number of // times N can be divided by distinct // powers of prime integers function maxDivisions(N) { // Stores the required count let cnt = 0; let range = Math.sqrt(N); // Loop to iterate in range [2, ?N] for (let i = 2; i <= range; i++) { // If i divides N if (N % i == 0) { let j = i; // Divide N with increasing // powers of i while (N % j == 0 && N) { N = N / j; // Update j j *= i; // Increment cnt cnt++; } // Remove the remaining power // of i to avoid repetition while (N % i == 0) { N /= i; } } } // Return Answer return cnt; } // Driver Code let N = 100; document.write(maxDivisions(N)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(?N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!