Smallest divisor of N closest to X

Approach - 2 (Efficient for Q queries)

This approach is efficient when we are required to answer Q queries.

Before moving to the approach, let’s learn the lower_bound function:

lower_bound function:

In C++, the lower bound() function returns an iterator pointing to the first element in the range [first, last) with a value greater than or equal to val.
In this approach, we will precompute the divisors of all the numbers from 1 to N by using a modified Sieve of Eratosthenes.
We will use a vector of vectors to store the divisors of all the numbers from 1 to N. Every i^th row of this contains all the divisors of the number i.
Now, we can efficiently find the smallest divisor of N closest to X using the binary search algorithm as all the divisors of N in the container is in a sorted manner. 
For finding the smallest divisor of N closest to X, we will use the inbuilt lower_bound function in the Nth row.

Must Read Lower Bound in C++

Steps of algorithm

• Create a vector of vectors divs of size MAXM=10000 to store the divisors from 1 to N.
• Precompute the divisor of all the numbers from 1 to N using the modified Sieve of Eratosthenes and store it in divs.
• Find the closest number from X in the Nth row using the lower bound function.
• After using the lower_bound(), if the iterator is pointing to the end of the Nth row. Print the last number of that row.
• Else check the previous number and the pointing number, print the smallest divisor of N closest to X from both of them.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

#define MAXM 100000

vector<vector<int> > divs(MAXM + 1);

void calculateDivisors()
{
    for (int i = 1; i <= MAXM; i++)
    {
        for (int j = i; j <= MAXM; j += i)
        {

            divs[j].push_back(i);
        }
    }
}

void closest_divisor(int n, int x)
{
    auto it = lower_bound(divs[n].begin(), divs[n].end(), x);

    if (it == divs[n].end())
    {
        it--;
        cout << *it << endl;
    }
    else {
        int diff = INT_MAX;

        diff = min(diff, abs(*it - x));

        if (it != divs[n].begin())
            it--;

        diff = min(diff, abs(*it - x));

        if (n % (x - diff) == 0)
            cout << x - diff << endl;
        else
            cout << x + diff << endl;
    }
}

int main()
{
    int N = 24;

    int Q;
    cin >> Q;

    calculateDivisors();
    
    while (Q--)
    {   
        int X;
        cin >> X;

        closest_divisor(N, X);
    }

}

Input

4 
20
17
6
9

Output

24
12
6
8

Complexity Analysis

Time complexity: O(max(n*log(logn), Q*logn)), as we are using a modified Sieve of Eratosthenes, where Q is the number of queries we need to answer.

Space complexity: O(MAXM), as we are using a vector of vectors of size MAXM+1, where MAXM is the maximum value of the number N for which we need to find the closest divisor.

FAQs

1. What is Sieve of Eratosthenes C++?
   It is used to generate prime numbers within a given range. An integer array with all elements is initialised to zero using this method. Each non-prime element's index is set to 1 for each non-prime element inside the nested loops. The prime numbers are those with a value of 0 in their index.
    
2. Is Sieve of Eratosthenes dynamic programming?
   Yes, we can consider Eratosthenes' Sieve to be an example of dynamic programming. All of the composite numbers will be subproblems.
    
3. Is binary searching a divide-and-conquer strategy?
   Instead of divide-and-conquer, binary search is a decrease-and-conquer algorithm. The Euclidean algorithm for computing the greatest common divisor of two numbers by reducing the numbers to smaller and smaller equivalent subproblems, which dates back several centuries BC, is another ancient decrease-and-conquer algorithm.
    
4. What is the purpose of the upper_bound function in C++?
   upper bound() is a C++ header-defined standard library function. It returns an iterator pointing to the first element greater than the value in the range [first, last], or last if none is found. The elements in the range must be sorted or at the very least partitioned in relation to val.

Key Takeaways

This article discussed the different approaches to finding the Smallest divisor of N closest to X. 
First, we discussed the better approach using the property of divisors, i.e. all divisors of a number exist in pairs, and an efficient approach using the modified sieve of Eratosthenes and binary search algorithm with a complete explanation of its implementation in C++.

Check out this problem - Next Smaller Element

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free! 
Thank you for reading!