Largest divisor of a number not divisible by another given number

Namachila November 19, 2025

0 1 7 minutes read

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 Q
void 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 Code
int main()
{
    // Given P and Q
    int P = 10, Q = 4;
 
    // Function Call
    findTheGreatestX(P, Q);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
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
    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 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 Rajput-Ji

Python3

# Python3 program to implement
# the above approach
from collections import defaultdict
 
# Function to find the largest number
# X such that it divides P but is not
# divisible by Q
def 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 Code
if __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 Q
function 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 Q
var P = 10, Q = 4;
 
// Function Call
findTheGreatestX(P, Q);
 
// This code is contributed by itsok
 
</script>

Output

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 zambiatek!