Find numbers in the range [L, R] that are coprime with all given Array elements

Implementation in C++

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

void coprime_with_array(int a[], int n, int L, int R)
{
    unordered_set<int> DIV;

    for (int i = 0; i < n; i++)
    {
        int elem = a[i];

        for (int j = 1; j <= sqrt(elem) + 1; j++)
        {
            if (elem % j == 0)
            {
                DIV.insert(j);
                DIV.insert(elem / j);
            }
        }
    }

    unordered_set<int> NUMS;

    for (int i = L; i <= R; i++)
        NUMS.insert(i);

    DIV.erase(1);

    for (auto x : DIV)
    {
        int i = 1;

        while (i * x <= R)
        {
            NUMS.erase(i * x);

            i++;
        }
    }

    for (auto x : NUMS)
    {
        cout << x << " ";
    }
}

int main()
{
    int a[] = { 7, 9, 4, 11, 22, 13, 16, 8, 24 };

    int L = 4, R = 18;

    int N = sizeof(a) / sizeof(a[0]);

    coprime_with_array(a, N, L, R);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

17 5

Complexity Analysis

Time complexity: O(n * sqrt(maxm)), as we are running a nested loop of size n and maxm, where n is the number of elements and maxm is the maximum number present in the given array.

Space complexity: O(max(R-L, n)), as we are using unordered sets of sizes n and R-L.

Also see, Euclid GCD Algorithm

Frequently Asked Questions

Q1. What do you mean by co-prime numbers?

Answer: Co-Prime Numbers are a collection of numbers that share no common factor other than one. This indicates that their HCF (Highest Common Factor) is 1. In order to form Co-Primes, there must be at least two Numbers. Coprime numbers are also known as relatively prime numbers.
 

Q2. How do you find all divisors of a number?

Answer: Exhaustive trial division is the most basic method for calculating divisors. To find the positive divisors for an integer n, divide n by each of the integers 1, 2, 3,..., n, and the ones that divide evenly form the set of positive divisors for n.
 

Q3. How to check if a set contains an element in C++?

Answer: The member function find() is used to check for the existence of an element in the set container (std::set or std::unordered set). If the specified element can be found, an iterator is returned; otherwise, an iterator to the container's end is returned.

Q4. In C++, how do you traverse a set?

Answer: Using Iterators to Iterate over a Set,

set::begin() returns an iterator that points to the set's first element.

On the other hand, set::end() returns an iterator that continues past the end of the set. 

To iterate a set forward, we must first create an iterator and then initialise it with set::begin ().

Key Takeaways

This article discussed the approach to finding the numbers in the range [L, R] that are coprime with all given array elements with complete explanation, examples for a better understanding and its implementation in C++.
Check out this problem - Maximum Product Subarray

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!