Given an array arr[] of N integers, the task is to find the largest divisor for each element in an array other than 1 and the number itself. If there is no such divisor, print -1.
Examples:
Input: arr[] = {5, 6, 7, 8, 9, 10}
Output: -1 3 -1 4 3 5
Divisors(5) = {1, 5}
-> Since there is no divisor other than 1 and the number itself, therefore largest divisor = -1
Divisors(6) = [1, 2, 3, 6]
-> largest divisor other than 1 and the number itself = 3
Divisors(7) = [1, 7]
-> Since there is no divisor other than 1 and the number itself, therefore largest divisor = -1
Divisors(8) = [1, 2, 4, 8]
-> largest divisor other than 1 and the number itself = 4
Divisors(9) = [1, 3, 9]
-> largest divisor other than 1 and the number itself = 3
Divisors(10) = [1, 2, 5, 10]
-> largest divisor other than 1 and the number itself = 5Input: arr[] = {15, 16, 17, 18, 19, 20, 21}
Output: 5 8 -1 9 -1 10 7
Naive approach: The idea is to iterate over all the array elements and find the largest divisor for each of the element using the approach discussed in this article.
Time Complexity: O(N * ?N)
Efficient approach: A better solution is to precompute the maximum divisor of the numbers from 2 to 105 and then just run a loop for array and print precomputed answer.
- Use Sieve of Eratosthenes to mark the prime numbers and store the smallest prime divisor of each number.
- Now largest divisor for any number will be number / smallest_prime_divisor.
- Find the Largest divisor for each number using the precomputed answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define int long long const int maxin = 100001; // Divisors array to keep track // of the maximum divisor int divisors[maxin]; // Function to pre-compute the prime // numbers and largest divisors void Calc_Max_Div( int arr[], int n) { // Visited array to keep // track of prime numbers bool vis[maxin]; memset (vis, 1, maxin); // 0 and 1 are not prime numbers vis[0] = vis[1] = 0; // Initialising divisors[i] = i for ( int i = 1; i <= maxin; i++) divisors[i] = i; // For all the numbers divisible by 2 // the maximum divisor will be number / 2 for ( int i = 4; i <= maxin; i += 2) { vis[i] = 0; divisors[i] = i / 2; } for ( int i = 3; i <= maxin; i += 2) { // If divisors[i] is not equal to i then // this means that divisors[i] contains // minimum prime divisor for the number if (divisors[i] != i) { // Update the answer to // i / smallest_prime_divisor[i] divisors[i] = i / divisors[i]; } // Condition if i is a prime number if (vis[i] == 1) { for ( int j = i * i; j < maxin; j += i) { vis[j] = 0; // If divisors[j] is equal to j then // this means that i is the first prime // divisor for j so we update divi[j] = i if (divisors[j] == j) divisors[j] = i; } } } for ( int i = 0; i < n; i++) { // If the current element is prime // then it has no divisors // other than 1 and itself if (divisors[arr[i]] == arr[i]) cout << "-1 " ; else cout << divisors[arr[i]] << " " ; } } // Driver code int32_t main() { int arr[] = { 5, 6, 7, 8, 9, 10 }; int n = sizeof (arr) / sizeof ( int ); Calc_Max_Div(arr, n); return 0; } |
Java
// Java implementation of the approach import java.io.*; public class GFG { final static int maxin = 10001 ; // Divisors array to keep track // of the maximum divisor static int divisors[] = new int [maxin + 1 ]; // Function to pre-compute the prime // numbers and largest divisors static void Calc_Max_Div( int arr[], int n) { // Visited array to keep // track of prime numbers int vis[] = new int [maxin + 1 ]; for ( int i = 0 ;i <maxin+ 1 ; i++) vis[i] = 1 ; // 0 and 1 are not prime numbers vis[ 0 ] = vis[ 1 ] = 0 ; // Initialising divisors[i] = i for ( int i = 1 ; i <= maxin; i++) divisors[i] = i; // For all the numbers divisible by 2 // the maximum divisor will be number / 2 for ( int i = 4 ; i <= maxin; i += 2 ) { vis[i] = 0 ; divisors[i] = i / 2 ; } for ( int i = 3 ; i <= maxin; i += 2 ) { // If divisors[i] is not equal to i then // this means that divisors[i] contains // minimum prime divisor for the number if (divisors[i] != i) { // Update the answer to // i / smallest_prime_divisor[i] divisors[i] = i / divisors[i]; } // Condition if i is a prime number if (vis[i] == 1 ) { for ( int j = i * i; j < maxin; j += i) { vis[j] = 0 ; // If divisors[j] is equal to j then // this means that i is the first prime // divisor for j so we update divi[j] = i if (divisors[j] == j) divisors[j] = i; } } } for ( int i = 0 ; i < n; i++) { // If the current element is prime // then it has no divisors // other than 1 and itself if (divisors[arr[i]] == arr[i]) System.out.print( "-1 " ); else System.out.print(divisors[arr[i]] + " " ); } } // Driver code public static void main (String[] args) { int []arr = { 5 , 6 , 7 , 8 , 9 , 10 }; int n = arr.length; Calc_Max_Div(arr, n); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach maxin = 100001 ; # Divisors array to keep track # of the maximum divisor divisors = [ 0 ] * (maxin + 1 ); # Function to pre-compute the prime # numbers and largest divisors def Calc_Max_Div(arr, n) : # Visited array to keep # track of prime numbers vis = [ 1 ] * (maxin + 1 ); # 0 and 1 are not prime numbers vis[ 0 ] = vis[ 1 ] = 0 ; # Initialising divisors[i] = i for i in range ( 1 , maxin + 1 ) : divisors[i] = i; # For all the numbers divisible by 2 # the maximum divisor will be number / 2 for i in range ( 4 , maxin + 1 , 2 ) : vis[i] = 0 ; divisors[i] = i / / 2 ; for i in range ( 3 , maxin + 1 , 2 ) : # If divisors[i] is not equal to i then # this means that divisors[i] contains # minimum prime divisor for the number if (divisors[i] ! = i) : # Update the answer to # i / smallest_prime_divisor[i] divisors[i] = i / / divisors[i]; # Condition if i is a prime number if (vis[i] = = 1 ) : for j in range ( i * i, maxin, i) : vis[j] = 0 ; # If divisors[j] is equal to j then # this means that i is the first prime # divisor for j so we update divi[j] = i if (divisors[j] = = j) : divisors[j] = i; for i in range (n) : # If the current element is prime # then it has no divisors # other than 1 and itself if (divisors[arr[i]] = = arr[i]) : print ( "-1 " , end = ""); else : print (divisors[arr[i]], end = " " ); # Driver code if __name__ = = "__main__" : arr = [ 5 , 6 , 7 , 8 , 9 , 10 ]; n = len (arr); Calc_Max_Div(arr, n); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System; class GFG { static int maxin = 10001; // Divisors array to keep track // of the maximum divisor static int []divisors = new int [maxin + 1]; // Function to pre-compute the prime // numbers and largest divisors static void Calc_Max_Div( int []arr, int n) { // Visited array to keep // track of prime numbers int []vis = new int [maxin + 1]; for ( int i = 0; i < maxin + 1 ; i++) vis[i] = 1; // 0 and 1 are not prime numbers vis[0] = vis[1] = 0; // Initialising divisors[i] = i for ( int i = 1; i <= maxin; i++) divisors[i] = i; // For all the numbers divisible by 2 // the maximum divisor will be number / 2 for ( int i = 4; i <= maxin; i += 2) { vis[i] = 0; divisors[i] = i / 2; } for ( int i = 3; i <= maxin; i += 2) { // If divisors[i] is not equal to i then // this means that divisors[i] contains // minimum prime divisor for the number if (divisors[i] != i) { // Update the answer to // i / smallest_prime_divisor[i] divisors[i] = i / divisors[i]; } // Condition if i is a prime number if (vis[i] == 1) { for ( int j = i * i; j < maxin; j += i) { vis[j] = 0; // If divisors[j] is equal to j then // this means that i is the first prime // divisor for j so we update divi[j] = i if (divisors[j] == j) divisors[j] = i; } } } for ( int i = 0; i < n; i++) { // If the current element is prime // then it has no divisors // other than 1 and itself if (divisors[arr[i]] == arr[i]) Console.Write( "-1 " ); else Console.Write(divisors[arr[i]] + " " ); } } // Driver code public static void Main() { int []arr = { 5, 6, 7, 8, 9, 10 }; int n = arr.Length; Calc_Max_Div(arr, n); } } // This code is contributed by AnkitRai01 |
Javascript
<script> // Javascript implementation of the approach var maxin = 100001; // Divisors array to keep track // of the maximum divisor var divisors = Array(maxin).fill(0); // Function to pre-compute the prime // numbers and largest divisors function Calc_Max_Div(arr, n) { // Visited array to keep // track of prime numbers var vis = Array(maxin).fill(1); // 0 and 1 are not prime numbers vis[0] = vis[1] = 0; var i,j; // Initialising divisors[i] = i for (i = 1; i <= maxin; i++) divisors[i] = i; // For all the numbers divisible by 2 // the maximum divisor will be number / 2 for (i = 4; i <= maxin; i += 2) { vis[i] = 0; divisors[i] = i / 2; } for (i = 3; i <= maxin; i += 2) { // If divisors[i] is not equal to i then // this means that divisors[i] contains // minimum prime divisor for the number if (divisors[i] != i) { // Update the answer to // i / smallest_prime_divisor[i] divisors[i] = i / divisors[i]; } // Condition if i is a prime number if (vis[i] == 1) { for (j = i * i; j < maxin; j += i) { vis[j] = 0; // If divisors[j] is equal to j then // this means that i is the first prime // divisor for j so we update divi[j] = i if (divisors[j] == j) divisors[j] = i; } } } for (i = 0; i < n; i++) { // If the current element is prime // then it has no divisors // other than 1 and itself if (divisors[arr[i]] == arr[i]) document.write( "-1 " ); else document.write(divisors[arr[i]] + " " ); } } // Driver code var arr = [ 5, 6, 7, 8, 9, 10 ]; var n = arr.length; Calc_Max_Div(arr, n); // This code is contributed by bgangwar59 </script> |
-1 3 -1 4 3 5
Time Complexity: O(N)
Auxiliary Space: O(100001)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!