Find minimum number to be divided to make a number a perfect square | C ++ program to find minimum number which divide n to make it a perfect square . ; Return the minimum number to be divided to make n a perfect square . ; Since 2 is only even prime , compute its power separately . ; If count is odd , it must be removed by dividing n by prime number . ; If count is odd , it must be removed by dividing n by prime number . ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMinNumber ( int n ) { int count = 0 , ans = 1 ; while ( n % 2 == 0 ) { count ++ ; n /= 2 ; } if ( count % 2 ) ans *= 2 ; for ( int i = 3 ; i <= sqrt ( n ) ; i += 2 ) { count = 0 ; while ( n % i == 0 ) { count ++ ; n /= i ; } if ( count % 2 ) ans *= i ; } if ( n > 2 ) ans *= n ; return ans ; } int main ( ) { int n = 72 ; cout << findMinNumber ( n ) << endl ; return 0 ; }