Given an integer N which denotes the number of divisors of any number, the task is to find the maximum prime divisors that are possible in number having N divisors.
Examples:
Input: N = 4
Output: 2Input: N = 8
Output: 3
Naive Approach: In this approach, the idea is to generate all the numbers having exactly N divisors and check for the maximum number of prime divisors. Below are the steps:
- Define a function is_prime(num) that takes an integer as input and returns True if it is prime, and False otherwise.
- Check if the number is less than 2, in which case it is not prime.
- Use a loop to check if the number is divisible by any integer from 2 up to its square root.
- If it is divisible by any integer, return False.
- If the loop completes without finding a divisor, return True.
Implementation:
C++
#include <iostream> #include <cmath> // Function to check if a number num is prime or not bool isPrime( int num) { if (num < 2) { return false ; } for ( int i = 2; i * i <= num; i++) { if (num % i == 0) { return false ; } } return true ; } // Function to count the number of prime divisors in num int countPrimes( int num) { int count = 0; for ( int i = 2; i * i <= num; i++) { if (num % i == 0) { if (isPrime(i)) { count++; } if (isPrime(num / i)) { count++; } } } return count; } // Function to find the maximum prime divisor of the number n int maxPrimeDivisorsBruteForce( int n) { int maxPrimes = 0; int maxNum = 0; for ( int num = 2; num < pow (10, n); num++) { int divisors = 0; for ( int i = 1; i <= num; i++) { if (num % i == 0) { divisors++; } } if (divisors == n) { int primeCount = countPrimes(num); if (primeCount > maxPrimes) { maxPrimes = primeCount; maxNum = num; } } } return maxPrimes; } int main() { int n = 4; int result = maxPrimeDivisorsBruteForce(n); std::cout << result << std::endl; return 0; } |
Java
public class MaxPrimeDivisorsBruteForce { // Function to check if a number num is prime or not static boolean isPrime( int num) { if (num < 2 ) { return false ; } for ( int i = 2 ; i * i <= num; i++) { if (num % i == 0 ) { return false ; } } return true ; } // Function to count the number of prime divisors in num static int countPrimes( int num) { int count = 0 ; for ( int i = 2 ; i * i <= num; i++) { if (num % i == 0 ) { if (isPrime(i)) { count++; } if (isPrime(num / i)) { count++; } } } return count; } // Function to find the maximum prime divisor of the number n static int maxPrimeDivisorsBruteForce( int n) { int maxPrimes = 0 ; int maxNum = 0 ; for ( int num = 2 ; num < Math.pow( 10 , n); num++) { int divisors = 0 ; for ( int i = 1 ; i <= num; i++) { if (num % i == 0 ) { divisors++; } } if (divisors == n) { int primeCount = countPrimes(num); if (primeCount > maxPrimes) { maxPrimes = primeCount; maxNum = num; } } } return maxPrimes; } public static void main(String[] args) { int n = 4 ; int result = maxPrimeDivisorsBruteForce(n); System.out.println(result); } } |
Python3
def is_prime(num): """Function to check if a number num is prime or not""" if num < 2 : return False for i in range ( 2 , int (num * * 0.5 ) + 1 ): if num % i = = 0 : return False return True def count_primes(num): """Function to count the number of prime divisors in num""" count = 0 for i in range ( 2 , int (num * * 0.5 ) + 1 ): if num % i = = 0 : while num % i = = 0 : num / / = i # Reduce num to its prime factor count + = 1 if num > 1 : count + = 1 # If num is a prime number return count def max_prime_divisors_optimized(n): """Function to find the maximum prime divisor of the number n""" max_primes = 0 max_num = 0 for num in range ( 2 , 10 * * n): divisors = 0 if num % 2 = = 0 : continue # Skip even numbers as they have more divisors for i in range ( 1 , int (num * * 0.5 ) + 1 ): if num % i = = 0 : divisors + = 1 if i ! = num / / i: # Avoid counting twice for perfect squares divisors + = 1 if divisors = = n: prime_count = count_primes(num) if prime_count > max_primes: max_primes = prime_count max_num = num return max_primes def main(): n = 4 result = max_prime_divisors_optimized(n) print (result) if __name__ = = "__main__" : main() |
C#
using System; public class MaxPrimeDivisorsBruteForce { // Function to check if a number num is prime or not static bool IsPrime( int num) { if (num < 2) { return false ; } for ( int i = 2; i * i <= num; i++) { if (num % i == 0) { return false ; } } return true ; } // Function to count the number of prime divisors in num static int CountPrimes( int num) { int count = 0; for ( int i = 2; i * i <= num; i++) { if (num % i == 0) { if (IsPrime(i)) { count++; } if (IsPrime(num / i)) { count++; } } } return count; } // Function to find the maximum prime divisor of the number n static int FindMaxPrimeDivisor( int n) { int maxPrimes = 0; for ( int num = 2; num < Math.Pow(10, n); num++) { int divisors = 0; for ( int i = 1; i <= num; i++) { if (num % i == 0) { divisors++; } } if (divisors == n) { int primeCount = CountPrimes(num); if (primeCount > maxPrimes) { maxPrimes = primeCount; } } } return maxPrimes; } public static void Main( string [] args) { int n = 4; int result = FindMaxPrimeDivisor(n); Console.WriteLine(result); } } |
Javascript
// Function to check if a number num is prime or not function isPrime(num) { if (num < 2) { return false ; } for (let i = 2; i * i <= num; i++) { if (num % i === 0) { return false ; } } return true ; } // Function to count the number of prime divisors in num function countPrimes(num) { let count = 0; for (let i = 2; i * i <= num; i++) { if (num % i === 0) { if (isPrime(i)) { count++; } if (isPrime(num / i)) { count++; } } } return count; } // Function to find the maximum prime divisor of the number n function maxPrimeDivisorsBruteForce(n) { let maxPrimes = 0; let maxNum = 0; for (let num = 2; num < Math.pow(10, n); num++) { let divisors = 0; for (let i = 1; i <= num; i++) { if (num % i === 0) { divisors++; } } if (divisors === n) { let primeCount = countPrimes(num); if (primeCount > maxPrimes) { maxPrimes = primeCount; maxNum = num; } } } return maxPrimes; } const n = 4; const result = maxPrimeDivisorsBruteForce(n); console.log(result); |
2
Time Complexity: O(N2 * log(N))
Space Complexity: O(N)
Approach: The idea is to find the prime factorization of the number N, then the sum of the powers of the prime divisors is the maximum possible prime divisors of a number can have with N divisors.
For Example:
Let the number of divisors of number be 4,
Then the possible numbers can be 6, 10, 15,...
Divisors of 6 = 1, 2, 3, 6
Total number of prime-divisors = 2 (2, 3)
Prime Factorization of 4 = 22
Sum of powers of prime factors = 2
Below is the implementation of the above approach:
C++
// C++ implementation to find the // maximum possible prime divisor // of a number can have N divisors #include <iostream> using namespace std; #define ll long long int // Function to find the // maximum possible prime divisors // of a number can have with N divisors void findMaxPrimeDivisor( int n){ int max_possible_prime = 0; // Number of time number // divided by 2 while (n % 2 == 0) { max_possible_prime++; n = n / 2; } // Divide by other prime numbers for ( int i = 3; i * i <= n; i = i + 2) { while (n % i == 0) { max_possible_prime++; n = n / i; } } // If the last number of also // prime then also include it if (n > 2) { max_possible_prime++; } cout << max_possible_prime << "\n" ; } // Driver Code int main() { int n = 4; // Function Call findMaxPrimeDivisor(n); return 0; } |
Java
// Java implementation to find the // maximum possible prime divisor // of a number can have N divisors import java.util.*; class GFG{ // Function to find the // maximum possible prime divisors // of a number can have with N divisors static void findMaxPrimeDivisor( int n) { int max_possible_prime = 0 ; // Number of time number // divided by 2 while (n % 2 == 0 ) { max_possible_prime++; n = n / 2 ; } // Divide by other prime numbers for ( int i = 3 ; i * i <= n; i = i + 2 ) { while (n % i == 0 ) { max_possible_prime++; n = n / i; } } // If the last number of also // prime then also include it if (n > 2 ) { max_possible_prime++; } System.out.print(max_possible_prime + "\n" ); } // Driver Code public static void main(String[] args) { int n = 4 ; // Function Call findMaxPrimeDivisor(n); } } // This code is contributed by amal kumar choubey |
Python3
# Python3 implementation to find the # maximum possible prime divisor # of a number can have N divisors # Function to find the maximum # possible prime divisors of a # number can have with N divisors def findMaxPrimeDivisor(n): max_possible_prime = 0 # Number of time number # divided by 2 while (n % 2 = = 0 ): max_possible_prime + = 1 n = n / / 2 # Divide by other prime numbers i = 3 while (i * i < = n): while (n % i = = 0 ): max_possible_prime + = 1 n = n / / i i = i + 2 # If the last number of also # prime then also include it if (n > 2 ): max_possible_prime + = 1 print (max_possible_prime) # Driver Code n = 4 # Function Call findMaxPrimeDivisor(n) # This code is contributed by SHUBHAMSINGH10 |
C#
// C# implementation to find the // maximum possible prime divisor // of a number can have N divisors using System; class GFG{ // Function to find the // maximum possible prime divisors // of a number can have with N divisors static void findMaxPrimeDivisor( int n) { int max_possible_prime = 0; // Number of time number // divided by 2 while (n % 2 == 0) { max_possible_prime++; n = n / 2; } // Divide by other prime numbers for ( int i = 3; i * i <= n; i = i + 2) { while (n % i == 0) { max_possible_prime++; n = n / i; } } // If the last number of also // prime then also include it if (n > 2) { max_possible_prime++; } Console.Write(max_possible_prime + "\n" ); } // Driver Code public static void Main(String[] args) { int n = 4; // Function Call findMaxPrimeDivisor(n); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // JavaScript implementation to find the // maximum possible prime divisor // of a number can have N divisors // Function to find the maximum // possible prime divisors of a // number can have with N divisors function findMaxPrimeDivisor(n) { let max_possible_prime = 0; // Number of time number // divided by 2 while (n % 2 == 0) { max_possible_prime++; n = Math.floor(n / 2); } // Divide by other prime numbers for (let i = 3; i * i <= n; i = i + 2) { while (n % i == 0) { max_possible_prime++; n = Math.floor(n / i); } } // If the last number of also // prime then also include it if (n > 2) { max_possible_prime++; } document.write(max_possible_prime + "\n" ); } // Driver Code let n = 4; // Function Call findMaxPrimeDivisor(n); // This code is contributed by Surbhi Tyagi. </script> |
2
Time Complexity: O(sqrt(N) * logN )
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!