Data Modelling & AI Data Structure & Algorithm

Largest Divisor of a Number not divisible by a perfect square

23 June 2025

0

Given a positive integer, N. Find the largest divisor of the given number that is not divisible by a perfect square greater than 1.

Examples:

Input : 12
Output : 6
Explanation : Divisors of 12 are 1, 2, 3, 4, 6 and 12. 
Since 12 is divisible by 4 (a perfect square), 
it can't be required divisor. 6 is not divisible 
by any perfect square.
 
Input :97
Output :97

A simple approach is to find all the divisors of the given number N by iterating up to the square root of N and keep them in sorted order(Descending) in a list. Here we are inserting them in a set in descending order to keep them sorted. Also, make a list of all perfect squares up to 10¹⁰ by iterating from 1 to 10⁵.
Now, for each divisor starting from the greatest one, check whether it is divisible by any perfect square in the list or not. If a divisor is not divisible by any perfect, simply return it as the answer.

Steps to solve the problem:

Initialize a variable m to n and a set s.
Insert 1 and n into the set s.
Iterate over all integers from 2 to the square root of n.
- If n is divisible by i, insert n/i and i into the set s, and divide m by i repeatedly until it is no longer divisible by i.
if m is greater than 1, insert m into the set s.
Initialize a vector vec to store all perfect squares up to a certain limit.
Iterate over each element d in the set s using a range-based for loop.
Initialize a variable divi to 0.
Iterate over each perfect square in vec that is less than or equal to d .
- Check if d is divisible by the current perfect square without a remainder using an if statement.
- If d is divisible by the current perfect square, set divi to 1 and break out of the for loop.
- If d is not divisible by any perfect square, return d as the answer.

Below is the implementation of the above approach.

C++

// C++ Program to find the largest
// divisor not divisible by any
// perfect square greater than 1
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 1e5;
 
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
int findLargestDivisor(int n)
{
    // set to store divisors in
    // descending order
    int m = n;
    set<int, greater<int> > s;
    s.insert(1);
    s.insert(n);
 
    for (int i = 2; i < sqrt(n) + 1; i++) {
        // If the number is divisible
        // by i, then insert it
        if (n % i == 0) {
            s.insert(n / i);
            s.insert(i);
            while (m % i == 0)
                m /= i;
        }
    }
 
    if (m > 1)
        s.insert(m);
 
    // Vector to store perfect squares
    vector<int> vec;
    for (int i = 2; i <= MAX; i++)
        vec.push_back(i * i);
 
    // Check for each divisor, if it is not
    // divisible by any perfect square,
    // simply return it as the answer.
    for (auto d : s) {
        int divi = 0;
        for (int j = 0; j < vec.size()
                        && vec[j] <= d;
             j++) {
            if (d % vec[j] == 0) {
                divi = 1;
                break;
            }
        }
        if (!divi)
            return d;
    }
}
 
// Driver Code
int main()
{
    int n = 12;
    cout << findLargestDivisor(n) << endl;
 
    n = 97;
    cout << findLargestDivisor(n) << endl;
    return 0;
}

Java

// Java Program to find the largest 
// divisor not divisible by any 
// perfect square greater than 1 
import java.util.*;
class Main{
     
static int MAX = (int)1e5; 
     
// Function to find the largest 
// divisor not divisible by any 
// perfect square greater than 1 
public static int findLargestDivisor(int n) 
{ 
  // set to store divisors in 
  // descending order 
  int m = n; 
  Set<Integer> s = 
      new HashSet<Integer>(); 
  s.add(1); 
  s.add(n); 
 
  for (int i = 2; 
           i < (int)Math.sqrt(n) + 1; i++) 
  { 
    // If the number is divisible 
    // by i, then insert it 
    if (n % i == 0) 
    { 
      s.add(n / i); 
      s.add(i); 
      while (m % i == 0) 
        m /= i; 
    } 
  } 
 
  if (m > 1) 
    s.add(m); 
 
  List<Integer> l = 
       new ArrayList<Integer>(s);
 
  Collections.sort(l); 
  Collections.reverse(l);
 
  // Vector to store
  // perfect squares 
  Vector<Integer> vec = 
         new Vector<Integer>(); 
 
  for (int i = 2; i <= MAX; i++) 
    vec.add(i * i); 
 
  // Check for each divisor, if 
  // it is not divisible by any 
  // perfect square, simply return 
  // it as the answer. 
  for (int d : l)
  {
    int divi = 0; 
     
    for (int j = 0; 
             j < vec.size() && 
             vec.get(j) <= d; j++) 
    { 
      if (d % vec.get(j) == 0) 
      { 
        divi = 1; 
        break; 
      } 
    } 
    if (divi == 0) 
      return d; 
  } 
  return 0;
} 
 
// Driver code    
public static void main(String[] args)
{
  int n = 12; 
  System.out.println(findLargestDivisor(n));
 
  n = 97; 
  System.out.println(findLargestDivisor(n));
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 Program to find the largest 
# divisor not divisible by any 
# perfect square greater than 1 
 
MAX = 10 ** 5
 
# Function to find the largest 
# divisor not divisible by any 
# perfect square greater than 1 
def findLargestDivisor(n): 
 
    # set to store divisors in 
    # descending order 
    m = n 
    s = set() 
    s.add(1) 
    s.add(n) 
 
    for i in range(2, int(n ** (0.5)) + 1): 
         
        # If the number is divisible 
        # by i, then insert it 
        if n % i == 0:
            s.add(n // i) 
            s.add(i) 
            while m % i == 0: 
                m //= i 
         
    if m > 1: 
        s.add(m) 
 
    # Vector to store perfect squares 
    vec = [i**2 for i in range(2, MAX + 1)] 
 
    # Check for each divisor, if it is not 
    # divisible by any perfect square, 
    # simply return it as the answer. 
    for d in sorted(s, reverse = True):
         
        divi, j = 0, 0
        while j < len(vec) and vec[j] <= d: 
 
            if d % vec[j] == 0: 
                divi = 1
                break
            j += 1       
         
        if not divi:
            return d 
 
# Driver Code 
if __name__ == "__main__":
 
    n = 12
    print(findLargestDivisor(n)) 
 
    n = 97
    print(findLargestDivisor(n)) 
     
# This code is contributed by Rituraj Jain

C#

// C# program to find the largest 
// divisor not divisible by any 
// perfect square greater than 1 
using System;
using System.Collections.Generic;
 
class GFG{
     
static int MAX = (int)1e5; 
 
// Function to find the largest 
// divisor not divisible by any 
// perfect square greater than 1 
static int findLargestDivisor(int n) 
{ 
     
    // Set to store divisors in 
    // descending order 
    int m = n; 
     
    HashSet<int> s = new HashSet<int>(); 
    s.Add(1); 
    s.Add(n); 
     
    for(int i = 2; 
            i < (int)Math.Sqrt(n) + 1;
            i++) 
    { 
         
        // If the number is divisible 
        // by i, then insert it 
        if (n % i == 0) 
        { 
            s.Add(n / i); 
            s.Add(i);
             
            while (m % i == 0) 
                m /= i; 
        } 
    } 
     
    if (m > 1) 
        s.Add(m); 
     
    List<int> l = new List<int>(s);
    l.Sort(); 
    l.Reverse();
     
    // Vector to store
    // perfect squares 
    List<int> vec = new List<int>();
     
    for(int i = 2; i <= MAX; i++) 
        vec.Add(i * i); 
     
    // Check for each divisor, if 
    // it is not divisible by any 
    // perfect square, simply return 
    // it as the answer. 
    foreach(int d in l) 
    {
        int divi = 0; 
         
        for(int j = 0; 
                j < vec.Count && vec[j] <= d;
                j++) 
        { 
            if (d % vec[j] == 0) 
            { 
                divi = 1; 
                break; 
            } 
        } 
        if (divi == 0) 
            return d; 
    } 
    return 0;
}  
 
// Driver code
static void Main()
{
    int n = 12; 
    Console.WriteLine(findLargestDivisor(n));
     
    n = 97; 
    Console.WriteLine(findLargestDivisor(n));
}
}
 
// This code is contributed by divyesh072019

Javascript

<script>
// Javascript Program to find the largest
// divisor not divisible by any
// perfect square greater than 1
 
let MAX = 100000;
 
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
function findLargestDivisor(n)
{
  // set to store divisors in
  // descending order
  let m = n;
  let s = new Set();
  s.add(1);
  s.add(n);
  
  for (let i = 2;
           i < Math.floor(Math.sqrt(n)) + 1; i++)
  {
    // If the number is divisible
    // by i, then insert it
    if (n % i == 0)
    {
      s.add(Math.floor(n / i));
      s.add(i);
      while (m % i == 0)
        m = Math.floor(m/i);
    }
  }
  
  if (m > 1)
    s.add(m);
  
  let l =Array.from(s);
  
  l.sort(function(a,b){return a-b;});
  l.reverse();
  // Vector to store
  // perfect squares
  let vec = [];
  
  for (let i = 2; i <= MAX; i++)
    vec.push(i * i);
  
  // Check for each divisor, if
  // it is not divisible by any
  // perfect square, simply return
  // it as the answer.
  for (let d=0;d<l.length;d++)
  {
    let divi = 0;
      
    for (let j = 0;
             j < vec.length &&
             vec[j] <= l[d]; j++)
    {
      if (l[d] % vec[j] == 0)
      {
        divi = 1;
        break;
      }
    }
    if (divi == 0)
      return l[d];
  }
  return 0;
}
 
// Driver code   
let n = 12;
document.write(findLargestDivisor(n)+"<br>");
 
n = 97;
document.write(findLargestDivisor(n)+"<br>");
     
     
// This code is contributed by rag2127
</script>

Output:

6
97

Time Complexity : O(sqrt(n)*logn)
Auxiliary Space: O(n)

An efficient approach is to divide n by i for every i such that (i * i) divides n.

C++

// Efficient C++ Program to find the 
// largest divisor not divisible by any
// perfect square greater than 1
#include <bits/stdc++.h>
using namespace std;
  
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
int findLargestDivisor(int n)
{
    for (int i = 2; i < sqrt(n) + 1; i++) {
         
        // If the number is divisible
        // by i*i, then remove one i
        while (n % (i * i) == 0) {
            n = n / i;
        }
    }
   
    // Now all squares are removed from n
    return n;    
}
  
// Driver Code
int main()
{
    int n = 12;
    cout << findLargestDivisor(n) << endl;
  
    n = 97;
    cout << findLargestDivisor(n) << endl;
    return 0;
}

Java

// Efficient Java Program to find the 
// largest divisor not divisible by any 
// perfect square greater than 1 
 
public class GFG
{
 
    // Function to find the largest 
    // divisor not divisible by any 
    // perfect square greater than 1 
    static int findLargestDivisor(int n) 
    { 
        for (int i = 2; i < Math.sqrt(n) + 1; i++) { 
             
            // If the number is divisible 
            // by i*i, then remove one i 
            while (n % (i * i) == 0) { 
                n = n / i; 
            } 
        } 
         
        // Now all squares are removed from n 
        return n;     
    } 
     
    // Driver Code 
    public static void main(String args[]) 
    { 
        int n = 12; 
        System.out.println(findLargestDivisor(n)) ;
     
        n = 97; 
        System.out.println(findLargestDivisor(n)) ;
     
    } 
    // This code is contributed
    // by Ryuga
}

Python3

# Efficient Python3 Program to find the 
# largest divisor not divisible by any
# perfect square greater than 1
import math
 
# Function to find the largest
# divisor not divisible by any
# perfect square greater than 1
def findLargestDivisor( n):
 
    for i in range (2, int(math.sqrt(n)) + 1) : 
         
        # If the number is divisible
        # by i*i, then remove one i
        while (n % (i * i) == 0) :
            n = n // i
     
    # Now all squares are removed from n
    return n
 
# Driver Code
if __name__ == "__main__":
 
    n = 12
    print (findLargestDivisor(n))
 
    n = 97
    print (findLargestDivisor(n))
 
# This code is contributed by ita_c

C#

// Efficient C# Program to find the 
// largest divisor not divisible by any 
// perfect square greater than 1 
using System;
public class GFG
{
 
    // Function to find the largest 
    // divisor not divisible by any 
    // perfect square greater than 1 
    static int findLargestDivisor(int n) 
    { 
        for (int i = 2; i < Math.Sqrt(n) + 1; i++) { 
             
            // If the number is divisible 
            // by i*i, then remove one i 
            while (n % (i * i) == 0) { 
                n = n / i; 
            } 
        } 
         
        // Now all squares are removed from n 
        return n;     
    } 
     
    // Driver Code 
    public static void Main() 
    { 
        int n = 12; 
        Console.WriteLine(findLargestDivisor(n)) ;
     
        n = 97; 
        Console.WriteLine(findLargestDivisor(n)) ;
     
    } 
}
    // This code is contributed
    // by Mukul Singh

PHP

<?php
// Efficient PHP Program to find the 
// largest divisor not divisible by 
// any perfect square greater than 1
 
// Function to find the largest
// divisor not divisible by any
// perfect square greater than 1
function findLargestDivisor($n)
{
    for ($i = 2; $i < sqrt($n) + 1; $i++)
    {
         
        // If the number is divisible
        // by i*i, then remove one i
        while ($n % ($i * $i) == 0)
        {
            $n = $n / $i;
        }
    }
 
    // Now all squares are removed from n
    return $n; 
}
 
// Driver Code
$n = 12;
echo(findLargestDivisor($n));
echo("\n");
 
$n = 97;
echo(findLargestDivisor($n)) ;
 
// This code is contributed 
// by Shivi_Aggarwal
?>

Javascript

<script>
    // Efficient Javascript Program to find the
    // largest divisor not divisible by any
    // perfect square greater than 1
     
    // Function to find the largest
    // divisor not divisible by any
    // perfect square greater than 1
    function findLargestDivisor(n)
    {
        for (let i = 2; i < Math.sqrt(n) + 1; i++) 
        {
 
            // If the number is divisible
            // by i*i, then remove one i
            while (n % (i * i) == 0) {
                n = n / i;
            }
        }
 
        // Now all squares are removed from n
        return n;   
    }
     
    let n = 12;
    document.write(findLargestDivisor(n) + "</br>");
   
    n = 97;
    document.write(findLargestDivisor(n) + "</br>");
     
    // This code is contributed by suresh07.
</script>

Output:

6
97

Time Complexity : O(sqrt(n))
Auxiliary Space: O(1)

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!

Largest Divisor of a Number not divisible by a perfect square

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

PHP

Javascript

7 Years, 2 Major Rebuilds, 40K+ GitHub Stars: The Rise of Milvus as the Leading Open-Source Vector Database

Gemini 3 Pro + Milvus: Building a More Robust RAG With Advanced Reasoning and Multimodal Power

Multimodal RAG Made Simple: RAG-Anything + Milvus Instead of 20 Separate Tools

LEAVE A REPLY Cancel reply

Most Popular

What’s going on with the Galaxy S26 Ultra? [Video]

Mobile’s next big thing is unraveling, it’s going to get messy, and it may already be too late to stop it

I used the Moto G 2026 and Samsung Galaxy A16, and only one makes sense for $200

Samsung’s Galaxy S26 series may offer a couple of software surprises

EDITOR PICKS

What’s going on with the Galaxy S26 Ultra? [Video]

Mobile’s next big thing is unraveling, it’s going to get messy, and it may already be too late to stop it

I used the Moto G 2026 and Samsung Galaxy A16, and only one makes sense for $200

POPULAR POSTS

What’s going on with the Galaxy S26 Ultra? [Video]

Mobile’s next big thing is unraveling, it’s going to get messy, and it may already be too late to stop it

I used the Moto G 2026 and Samsung Galaxy A16, and only one makes sense for $200

POPULAR CATEGORY

ABOUT US

FOLLOW US