Tutorialspoint.dev

Find minimum number to be divided to make a number a perfect square

Given a positive integer n. Find the minimum number which divide n to make it a perfect square.

Examples:

Input : n = 50
Output : 2
By Dividing n by 2, we get which is a perfect square.

Input : n = 6
Output : 6
By Dividing n by 6, we get which is a perfect square.

Input : n = 36
Output : 1



A number is perfect square if all prime factors appear even number of times. The idea is to find the prime factor of n and find each prime factor power. Now, find and multiply all the prime factor whose power is odd. The resultant of the multiplication is the answer.

C++

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

Java

// Java program to find minimum number 
// which divide n to make it a perfect square.
  
class GFG
{
    // Return the minimum number to be 
    // divided to make n a perfect square.
    static int findMinNumber(int n)
    {
        int count = 0, ans = 1;
      
        // Since 2 is only even prime, 
        // compute its power seprately.
        while (n % 2 == 0)
        {
            count++;
            n /= 2;
        }
      
        // If count is odd, it must be removed by dividing
        // n by prime number.
        if (count % 2 == 1)
            ans *= 2;
      
        for (int i = 3; i <= Math.sqrt(n); i += 2)
        {
            count = 0;
            while (n % i == 0)
            {
                count++;
                n /= i;
            }
      
            // If count is odd, it must be removed by
            // dividing n by prime number.
            if (count % 2 == 1)
                ans *= i;
        }
      
        if (n > 2)
            ans *= n;
      
        return ans;
    }
  
    // Driver code
    public static void main (String[] args)
    {
        int n = 72;
        System.out.println(findMinNumber(n));
    }
}
  
// This code is contributed by Anant Agarwal.

Python3

# Python program to find 
# minimum number which 
# divide n to make it a 
# perfect square.
import math
  
# Return the minimum 
# number to be divided 
# to make n a perfect 
# square.
def findMinNumber(n):
    count = 0
    ans = 1
  
    # Since 2 is only 
    # even prime, compute 
    # its power seprately.
    while n % 2 == 0:
        count += 1
        n //= 2
  
    # If count is odd, 
    # it must be removed
    # by dividing n by 
    # prime number.
    if count % 2 is not 0:
        ans *= 2
  
    for i in range(3, (int)(math.sqrt(n)) + 1, 2):
        count = 0
        while n % i == 0:
            count += 1
            n //= i
  
        # If count is odd, it 
        # must be removed by 
        # dividing n by prime 
        # number.
        if count % 2 is not 0:
            ans *= i
  
    if n > 2:
        ans *= n
  
    return ans
  
# Driver Code
n = 72
print(findMinNumber(n))
  
# This code is contributed
# by Sanjit_Prasad.

C#

// C# program to find minimum 
// number which divide n to
// make it a perfect square.
using System;
  
class GFG
{
      
    // Return the minimum number
    // to be divided to make 
    // n a perfect square.
    static int findMinNumber(int n)
    {
        int count = 0, ans = 1;
      
        // Since 2 is only even prime, 
        // compute its power seprately.
        while (n % 2 == 0)
        {
            count++;
            n /= 2;
        }
      
        // If count is odd, it must 
        // be removed by dividing
        // n by prime number.
        if (count % 2 == 1)
            ans *= 2;
      
        for (int i = 3; i <= Math.Sqrt(n); 
                                  i += 2)
        {
            count = 0;
            while (n % i == 0)
            {
                count++;
                n /= i;
            }
      
            // If count is odd, it must 
            // be removed by dividing n
            // by prime number.
            if (count % 2 == 1)
                ans *= i;
        }
      
        if (n > 2)
            ans *= n;
      
        return ans;
    }
  
    // Driver code
    public static void Main ()
    {
        int n = 72;
        Console.WriteLine(findMinNumber(n));
    }
}
  
// This code is contributed by vt_m.

PHP

<?php
// PHP 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.
function findMinNumber($n)
{
    $count = 0;
    $ans = 1;
  
    // Since 2 is only 
    // even prime, 
    // compute its
    // power seprately.
    while ($n % 2 == 0)
    {
        $count++;
        $n /= 2;
    }
  
    // If count is odd, 
    // it must be removed 
    // by dividing n by 
    // prime number.
    if ($count % 2)
        $ans *= 2;
  
    for ($i = 3; $i <= sqrt($n); $i += 2)
    {
        $count = 0;
        while ($n % $i == 0)
        {
            $count++;
            $n /= $i;
        }
  
        // If count is odd, 
        // it must be removed
        // by dividing n by 
        // prime number.
        if ($count % 2)
            $ans *= $i;
    }
  
    if ($n > 2)
        $ans *= $n;
  
    return $ans;
}
  
    // Driver Code
    $n = 72;
    echo findMinNumber($n), " ";
      
// This code is contributed by ajit.
?>


Output:

2

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter