Given two positive integers P and Q, the task is to largest divisor of P which is not divisible by Q.
Examples:
Input: P = 10, Q = 4
Output: 10
Explanation: 10 is the largest number which divides 10 but not divisible by 4.Input: P = 12, Q = 6
Output: 4
Explanation: 4 is the largest number which divides 12 but not divisible by 6.
Approach: The simplest approach is to find all the divisors of P and obtain the greatest of these divisors, which is not divisible by Q.
Time Complexity: O(?P)
Auxiliary Space: O(1)
Alternate Approach: Follow the steps below to solve the problem:
- Store the count of frequencies of prime factors of Q in a HashMap divisors.
- Initialize a variable, say ans, to store the greatest number X, such that X divides P but is not divisible by Q.
- Iterate through all divisors of Q and perform the following steps:
- Store the count of frequencies of the current prime divisor in a variable, say frequency.
- Store the count of frequencies of the current prime divisor on dividing P in a variable, say cur, and initialize num as the current prime divisor * (frequency – cur + 1).
- If the value of cur is less than frequency, then update the variable ans to P and break out of the loop.
- Otherwise, divide P with num and store the result in a variable, say tempAns.
- After completing the above steps, update the value of ans to the maximum of ans and tempAns.
- After completing the above steps, print the value of ans as the maximum possible result.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the largest number// X such that it divides P but is not// divisible by Qvoid findTheGreatestX(int P, int Q){ // Stores the frequency count of // of all Prime Factors map<int, int> divisors; for (int i = 2; i * i <= Q; i++) { while (Q % i == 0 and Q > 1) { Q /= i; // Increment the frequency // of the current prime factor divisors[i]++; } } // If Q is a prime factor if (Q > 1) divisors[Q]++; // Stores the desired result int ans = 0; // Iterate through all divisors of Q for (auto i : divisors) { int frequency = i.second; int temp = P; // Stores the frequency count // of current prime divisor on // dividing P int cur = 0; while (temp % i.first == 0) { temp /= i.first; // Count the frequency of the // current prime factor cur++; } // If cur is less than frequency // then P is the final result if (cur < frequency) { ans = P; break; } temp = P; // Iterate to get temporary answer for (int j = cur; j >= frequency; j--) { temp /= i.first; } // Update current answer ans = max(temp, ans); } // Print the desired result cout << ans;}// Driver Codeint main(){ // Given P and Q int P = 10, Q = 4; // Function Call findTheGreatestX(P, Q); return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to find the largest number// X such that it divides P but is not// divisible by Qstatic void findTheGreatestX(int P, int Q){ // Stores the frequency count of // of all Prime Factors HashMap<Integer, Integer> divisors = new HashMap<>(); for(int i = 2; i * i <= Q; i++) { while (Q % i == 0 && Q > 1) { Q /= i; // Increment the frequency // of the current prime factor if (divisors.containsKey(i)) { divisors.put(i, divisors.get(i) + 1); } else { divisors.put(i, 1); } } } // If Q is a prime factor if (Q > 1) if (divisors.containsKey(Q)) { divisors.put(Q, divisors.get(Q) + 1); } else { divisors.put(Q, 1); } // Stores the desired result int ans = 0; // Iterate through all divisors of Q for(Map.Entry<Integer, Integer> i : divisors.entrySet()) { int frequency = i.getValue(); int temp = P; // Stores the frequency count // of current prime divisor on // dividing P int cur = 0; while (temp % i.getKey() == 0) { temp /= i.getKey(); // Count the frequency of the // current prime factor cur++; } // If cur is less than frequency // then P is the final result if (cur < frequency) { ans = P; break; } temp = P; // Iterate to get temporary answer for(int j = cur; j >= frequency; j--) { temp /= i.getKey(); } // Update current answer ans = Math.max(temp, ans); } // Print the desired result System.out.print(ans);}// Driver Codepublic static void main(String[] args){ // Given P and Q int P = 10, Q = 4; // Function Call findTheGreatestX(P, Q);}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program to implement# the above approachfrom collections import defaultdict# Function to find the largest number# X such that it divides P but is not# divisible by Qdef findTheGreatestX(P, Q): # Stores the frequency count of # of all Prime Factors divisors = defaultdict(int) i = 2 while i * i <= Q: while (Q % i == 0 and Q > 1): Q //= i # Increment the frequency # of the current prime factor divisors[i] += 1 i += 1 # If Q is a prime factor if (Q > 1): divisors[Q] += 1 # Stores the desired result ans = 0 # Iterate through all divisors of Q for i in divisors: frequency = divisors[i] temp = P # Stores the frequency count # of current prime divisor on # dividing P cur = 0 while (temp % i == 0): temp //= i # Count the frequency of the # current prime factor cur += 1 # If cur is less than frequency # then P is the final result if (cur < frequency): ans = P break temp = P # Iterate to get temporary answer for j in range(cur, frequency-1, -1): temp //= i # Update current answer ans = max(temp, ans) # Print the desired result print(ans)# Driver Codeif __name__ == "__main__": # Given P and Q P = 10 Q = 4 # Function Call findTheGreatestX(P, Q) # This code is contributed by chitranayal |
C#
// C# program to implement // the above approach using System.Collections.Generic; using System; using System.Linq;class GFG{// Function to find the largest number // X such that it divides P but is not // divisible by Q static void findTheGreatestX(int P, int Q) { // Stores the frequency count of // of all Prime Factors Dictionary<int, int> divisers = new Dictionary<int, int>(); for(int i = 2; i * i <= Q; i++) { while (Q % i == 0 && Q > 1) { Q /= i; // Increment the frequency // of the current prime factor if (divisers.ContainsKey(i)) divisers[i]++; else divisers[i] = 1; } } // If Q is a prime factor if (Q > 1) { if (divisers.ContainsKey(Q)) divisers[Q]++; else divisers[Q] = 1; } // Stores the desired result int ans = 0; var val = divisers.Keys.ToList(); // Iterate through all divisors of Q foreach(var key in val) { int frequency = divisers[key]; int temp = P; // Stores the frequency count // of current prime divisor on // dividing P int cur = 0; while (temp % key == 0) { temp /= key; // Count the frequency of the // current prime factor cur++; } // If cur is less than frequency // then P is the final result if (cur < frequency) { ans = P; break; } temp = P; // Iterate to get temporary answer for(int j = cur; j >= frequency; j--) { temp /= key; } // Update current answer ans = Math.Max(temp, ans); } // Print the desired result Console.WriteLine(ans); } // Driver Code public static void Main(String[] args) { // Given P and Q int P = 10, Q = 4; // Function Call findTheGreatestX(P, Q);} }// This code is contributed by Stream_Cipher |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the largest number// X such that it divides P but is not// divisible by Qfunction findTheGreatestX(P, Q){ // Stores the frequency count of // of all Prime Factors var divisors = new Map(); for(var i = 2; i * i <= Q; i++) { while (Q % i == 0 && Q > 1) { Q = parseInt(Q / i); // Increment the frequency // of the current prime factor if (divisors.has(i)) divisors.set(i, divisors.get(i) + 1) else divisors.set(i, 1) } } // If Q is a prime factor if (Q > 1) if (divisors.has(Q)) divisors.set(Q, divisors.get(Q) + 1) else divisors.set(Q, 1) // Stores the desired result var ans = 0; // Iterate through all divisors of Q divisors.forEach((value, key) => { var frequency = value; var temp = P; // Stores the frequency count // of current prime divisor on // dividing P var cur = 0; while (temp % key == 0) { temp = parseInt(temp / key); // Count the frequency of the // current prime factor cur++; } // If cur is less than frequency // then P is the final result if (cur < frequency) { ans = P; } temp = P; // Iterate to get temporary answer for(var j = cur; j >= frequency; j--) { temp = parseInt(temp / key); } // Update current answer ans = Math.max(temp, ans); }); // Print the desired result document.write(ans);}// Driver Code// Given P and Qvar P = 10, Q = 4;// Function CallfindTheGreatestX(P, Q);// This code is contributed by itsok</script> |
Output
10
Time Complexity: O(sqrt(Q) + log(P) * log(Q))
Auxiliary Space: O(Q)
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!
