Largest Divisor of a Number not divisible by a perfect square | Java 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
import java . util . * ; class Main { static int MAX = ( int ) 1e5 ; public static int findLargestDivisor ( int n ) { 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 ( 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 < Integer > vec = new Vector < Integer > ( ) ; for ( int i = 2 ; i <= MAX ; i ++ ) vec . add ( i * i ) ; 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 ; } public static void main ( String [ ] args ) { int n = 12 ; System . out . println ( findLargestDivisor ( n ) ) ; n = 97 ; System . out . println ( findLargestDivisor ( n ) ) ; } }