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
using System ; using System . Collections . Generic ; class GFG { static int MAX = ( int ) 1e5 ; static int findLargestDivisor ( int n ) { 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 ( 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 ( ) ; List < int > vec = new List < int > ( ) ; for ( int i = 2 ; i <= MAX ; i ++ ) vec . Add ( i * i ) ; 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 ; } static void Main ( ) { int n = 12 ; Console . WriteLine ( findLargestDivisor ( n ) ) ; n = 97 ; Console . WriteLine ( findLargestDivisor ( n ) ) ; } }