Given a positive integer N, the task is to find the total number of distinct power of prime factor of the given number N.
Examples:
Input: N = 216
Output: 4
Explanation:
216 can be expressed as 2 * 22 * 3 * 32.
The factors satisfying the conditions are 2, 22, 3 and 32 as all of them are written as distinct positive powers of prime factors.
Input: N = 24
Output: 3
Explanation:
24 can be expressed as 2 * 22 * 3
Approach: The idea is to find all the prime factors of N and how many times each prime factor divides N.
Suppose the prime factor ‘p’ divides N ‘z’ times, then the required distinct prime factors are p, p2, …, pi.
To find the number of distinct primes factor for prime number p find the minimum value of i such that (1 + 2 + …. + i) ? z.
Therefore, for each prime number dividing N K number of times, find the minimum value of i such that (1 + 2 + …. + i) ? K.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count the number // of distinct positive power of // prime factor of integer N int countFac( int n) { int m = n; int count = 0; // Iterate for all prime factor for ( int i = 2; (i * i) <= m; ++i) { int total = 0; // If it is a prime factor, // count the total number // of times it divides n. while (n % i == 0) { n /= i; ++total; } int temp = 0; // Find the Number of distinct // possible positive numbers for ( int j = 1; (temp + j) <= total; ++j) { temp += j; ++count; } } if (n != 1) ++count; // Return the final count return count; } // Driver Code int main() { // Given Number N int N = 24; // Function Call cout << countFac(N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to count the number // of distinct positive power of // prime factor of integer N static int countFac( int n) { int m = n; int count = 0 ; // Iterate for all prime factor for ( int i = 2 ; (i * i) <= m; ++i) { int total = 0 ; // If it is a prime factor, // count the total number // of times it divides n. while (n % i == 0 ) { n /= i; ++total; } int temp = 0 ; // Find the Number of distinct // possible positive numbers for ( int j = 1 ; (temp + j) <= total; ++j) { temp += j; ++count; } } if (n != 1 ) ++count; // Return the final count return count; } // Driver code public static void main(String[] args) { // Given Number N int N = 24 ; // Function Call System.out.println(countFac(N)); } } // This code is contributed by Pratima Pandey |
Python3
# Python3 program for the above approach # Function to count the number # of distinct positive power of # prime factor of integer N def countFac(n): m = n count = 0 # Iterate for all prime factor i = 2 while ((i * i) < = m): total = 0 # If it is a prime factor, # count the total number # of times it divides n. while (n % i = = 0 ): n / = i total + = 1 temp = 0 # Find the Number of distinct # possible positive numbers j = 1 while ((temp + j) < = total): temp + = j count + = 1 j + = 1 i + = 1 if (n ! = 1 ): count + = 1 # Return the final count return count # Driver Code # Given number N N = 24 # Function call print (countFac(N)) # This code is contributed by sanjoy_62 |
C#
// C# program for the above approach using System; class GFG{ // Function to count the number // of distinct positive power of // prime factor of integer N static int countFac( int n) { int m = n; int count = 0; // Iterate for all prime factor for ( int i = 2; (i * i) <= m; ++i) { int total = 0; // If it is a prime factor, // count the total number // of times it divides n. while (n % i == 0) { n /= i; ++total; } int temp = 0; // Find the Number of distinct // possible positive numbers for ( int j = 1; (temp + j) <= total; ++j) { temp += j; ++count; } } if (n != 1) ++count; // Return the final count return count; } // Driver code public static void Main() { // Given Number N int N = 24; // Function Call Console.Write(countFac(N)); } } // This code is contributed by Code_Mech |
Javascript
<script> // Javascript program for the above approach // Function to count the number // of distinct positive power of // prime factor of integer N function countFac(n) { var m = n; var count = 0; // Iterate for all prime factor for ( var i = 2; (i * i) <= m; ++i) { var total = 0; // If it is a prime factor, // count the total number // of times it divides n. while (n % i == 0) { n /= i; ++total; } var temp = 0; // Find the Number of distinct // possible positive numbers for ( var j = 1; (temp + j) <= total; ++j) { temp += j; ++count; } } if (n != 1) ++count; // Return the final count return count; } // Driver code // Given Number N var N = 24; // Function Call document.write(countFac(N)); // This code is contributed by Khushboogoyal499 </script> |
3
Time complexity: O(sqrt(N))
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!