Largest Divisor of a Number not divisible by a perfect square | C ++ 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 ; set to store divisors in descending order ; If the number is divisible by i , then insert it ; Vector to store perfect squares ; Check for each divisor , if it is not divisible by any perfect square , simply return it as the answer . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 1e5 ; int findLargestDivisor ( int n ) { int m = n ; set < int , greater < int > > s ; s . insert ( 1 ) ; s . insert ( n ) ; for ( int i = 2 ; i < sqrt ( n ) + 1 ; i ++ ) { if ( n % i == 0 ) { s . insert ( n / i ) ; s . insert ( i ) ; while ( m % i == 0 ) m /= i ; } } if ( m > 1 ) s . insert ( m ) ; vector < int > vec ; for ( int i = 2 ; i <= MAX ; i ++ ) vec . push_back ( i * i ) ; 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 ; } } int main ( ) { int n = 12 ; cout << findLargestDivisor ( n ) << endl ; n = 97 ; cout << findLargestDivisor ( n ) << endl ; return 0 ; }