Find the largest good number in the divisors of given number N
Given a number N. The task is to find the largest good number among the divisors of a given number N. A number X is defined as the good number if there is no such positive integer a > 1, such that a^2 is a divisor of X.
Examples:
Input: N = 10 Output: 10 In 1, 2, 5, 10. 10 is the largest good number Input: N = 12 Output: 6 In 1, 2, 3, 4, 6, 12. 6 is the largest good number
Approach: Find all prime divisors of N. Assume they are p1, p2, …, pk (in O(sqrt(n)) time complexity). If the answer is a, then we know that for each 1 <= I <= k, obviously, a is not divisible by pi^2 (and all greater powers of pi). So a <= p1 × p2 ×… × pk. And we know that p1 × p2 × … × pk is itself a good number. So, the answer is p1 × p2 ×…× pk.
Below is the implementation of the above approach:
C++
// CPP program to find the largest, good // number in the divisors of given number N. #include <bits/stdc++.h> using namespace std; // function to return distinct prime factors vector< int > PrimeFactors( int n) { // to store distinct prime factors vector< int > v; int x = n; // run a loop upto sqrt(n) for ( int i = 2; i * i <= n; i++) { if (x % i == 0) { // place this prime factor in vector v.push_back(i); while (x % i == 0) x /= i; } } // This condition is to handle the case when n // is a prime number greater than 1 if (x > 1) v.push_back(x); return v; } // function that returns good number int GoodNumber( int n) { // distinct prime factors vector< int > v = PrimeFactors(n); // to store answer int ans = 1; // product of all distinct prime // factors is required answer for ( int i = 0; i < v.size(); i++) ans *= v[i]; return ans; } // Driver code int main() { int n = 12; // function call cout << GoodNumber(n); return 0; } |
Java
// Java program to find the largest, good // number in the divisors of given number N. import java.util.*; class GFG { // function to return distinct prime factors static Vector<Integer> PrimeFactors( int n) { // to store distinct prime factors Vector<Integer> v = new Vector<Integer>(); int x = n; // run a loop upto sqrt(n) for ( int i = 2 ; i * i <= n; i++) { if (x % i == 0 ) { // place this prime factor in vector v.add(i); while (x % i == 0 ) x /= i; } } // This condition is to handle the case when n // is a prime number greater than 1 if (x > 1 ) v.add(x); return v; } // function that returns good number static int GoodNumber( int n) { // distinct prime factors Vector<Integer> v = new Vector<Integer>(PrimeFactors(n)); // to store answer int ans = 1 ; // product of all distinct prime // factors is required answer for ( int i = 0 ; i < v.size(); i++) ans *= v.get(i); return ans; } // Driver code public static void main(String[] args) { int n = 12 ; // function call System.out.println(GoodNumber(n)); } } // This code is contributed by ihritik |
Python 3
# Python 3 program to find the # largest, good number in the # divisors of given number N. # function to return distinct # prime factors def PrimeFactors(n): # to store distinct # prime factors v = [] x = n # run a loop upto sqrt(n) i = 2 while (i * i < = n): if (x % i = = 0 ) : # place this prime factor # in vector v.append(i) while (x % i = = 0 ): x / / = i i + = 1 # This condition is to handle # the case when n is a prime # number greater than 1 if (x > 1 ): v.append(x) return v # function that returns good number def GoodNumber(n): # distinct prime factors v = PrimeFactors(n) # to store answer ans = 1 # product of all distinct prime # factors is required answer for i in range ( len (v)): ans * = v[i] return ans # Driver code if __name__ = = "__main__" : n = 12 # function call print (GoodNumber(n)) # This code is contributed # by ChitraNayal |
C#
// C# program to find the largest, good // number in the divisors of given number N. using System; using System.Collections.Generic; public class GFG { // function to return distinct prime factors static List< int > PrimeFactors( int n) { // to store distinct prime factors List< int > v = new List< int >(); int x = n; // run a loop upto sqrt(n) for ( int i = 2; i * i <= n; i++) { if (x % i == 0) { // place this prime factor in vector v.Add(i); while (x % i == 0) x /= i; } } // This condition is to handle the case when n // is a prime number greater than 1 if (x > 1) v.Add(x); return v; } // function that returns good number static int GoodNumber( int n) { // distinct prime factors List< int > v = new List< int >(PrimeFactors(n)); // to store answer int ans = 1; // product of all distinct prime // factors is required answer for ( int i = 0; i < v.Count; i++) ans *= v[i]; return ans; } // Driver code public static void Main(String[] args) { int n = 12; // function call Console.WriteLine(GoodNumber(n)); } } // This code has been contributed by 29AjayKumar |
PHP
<?php // PHP program to find the largest, good // number in the divisors of given number N. // function to return distinct prime factors function PrimeFactors( $n ) { // to store distinct prime factors $v = array (); $x = $n ; // run a loop upto sqrt(n) for ( $i = 2; $i * $i <= $n ; $i ++) { if ( $x % $i == 0) { // place this prime factor in vector array_push ( $v , $i ); while ( $x % $i == 0) $x /= $i ; } } // This condition is to handle the case when n // is a prime number greater than 1 if ( $x > 1) array_push ( $v , $x ); return $v ; } // function that returns good number function GoodNumber( $n ) { // distinct prime factors $v = PrimeFactors( $n ); // to store answer $ans = 1; // product of all distinct prime // factors is required answer for ( $i = 0; $i < count ( $v ); $i ++) $ans *= $v [ $i ]; return $ans ; } // Driver code $n = 12; // function call echo GoodNumber( $n ); // This code is contributed by Rajput-Ji ?> |
Javascript
<script> // Javascript program to find the largest, good // number in the divisors of given number N. // function to return distinct prime factors function PrimeFactors(n) { // to store distinct prime factors let v = []; let x = n; // run a loop upto sqrt(n) for (let i = 2; i * i <= n; i++) { if (x % i == 0) { // place this prime factor in vector v.push(i); while (x % i == 0) x = Math.floor(x/i); } } // This condition is to handle the case when n // is a prime number greater than 1 if (x > 1) v.push(x); return v; } // function that returns good number function GoodNumber(n) { // distinct prime factors let v = PrimeFactors(n); // to store answer let ans = 1; // product of all distinct prime // factors is required answer for (let i = 0; i < v.length; i++) ans *= v[i]; return ans; } // Driver code let n = 12; // function call document.write(GoodNumber(n)); // This code is contributed by rag2127 </script> |
6
Time Complexity : O(sqrt(n) + k) ,where n is given number and k is number of distinct prime factors.
Space Complexity : O(k) ,to store distinct prime factors.
Contact Us