Largest Divisor for each element in an array other than 1 and the number itself

0 0 8 minutes read

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 = 5

Input: 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 10⁵ 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>

Output:

-1 3 -1 4 3 5

Time Complexity: O(N)
Auxiliary Space: O(100001)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!