The smallest integer that divides every element in a given array > 1: using C++

In this article, we are given an array of integers and we have to find the smallest number greater than 1 that divides all the elements in the array. For example, let us consider an example array [30, 90, 15, 45, 165].

vector<int> arr = {30, 90, 15, 45, 165};
result = solve(arr);

Now we can find the greatest common divisor (GCD) of the arrays. If the result is 1, which means that only 1 can divide the entire array, we can return -1 or "Not possible." If the result is an integer, then this integer divides the entire array. However, this integer may not be the smallest integer that divides the entire array. Interestingly, factors of this integer also divide the entire array, which makes sense. So, if we can find the smallest factor of this integer (GCD), we have the smallest integer that divides the entire array. So, in short, we need to find the Greatest Common Divisor (GCD) of the arrays and then the smallest factor is our answer.

Example

Example

The following C code can find the smallest integer greater than 1 that can divide all elements in the array. This can be achieved by finding the greatest common divisor of a list of elements -

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int divisor(int x) {
   if (x%2 == 0) {
      return 2;
   }
   for (int i=3;i*i<=x;i+=2) {
      if (x%i == 0) {
         return i;
      }
   }
   return x;
}
int solve(vector<int> arr) {
   int gcd = 0;
   for (int i=0;i<arr.size();i++) {
      gcd = __gcd(gcd, arr[i]);
   }
   return divisor(gcd);
}
int main() {
   vector<int> arr = {30, 90, 15, 45, 165};
   cout << solve(arr);
   return 0;
}

Output

3

Example

Example

If there are many queries, finding the prime factors of a number will be repeated. Using the sieve method, we can calculate the prime factors of a number.

In C, another implementation method of finding the smallest number greater than 1 is as follows:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 100005;
vector<int> prime(MAX, 0);
void sieve() {
   prime[0] = 1;
   prime[1] = -1;
   for (int i=2; i*i<MAX;i++) {
      if (prime[i] == 0) {
         for (int j=i*2;j<MAX;j+=i) {
            if (prime[j] == 0) {
               prime[j] = i;
            }
         }
      }
   }
   for (int i=2; i<MAX;i++) {
      if (!prime[i]) {
         prime[i] = i;
      }
   }
}
int solve(vector<int> arr) {
   int gcd = 0;
   for (int i=0; i<arr.size();i++) {
      gcd = __gcd(gcd, arr[i]);
   }
   return prime[gcd];
}
int main() {
   sieve();
   vector<int> arr = { 30, 90, 15, 45, 165 };
   cout << solve(arr);
   return 0;
}

Output

3

in conclusion

We used the sqrt(n) method to obtain the minimum factor. This can be optimized, I leave it to you to try. The time complexity is O(sqrt(n)). In the second method, the time complexity will be that of the sieve method, which is O(nlog(log(n))). Note that we can find the upper limit of the sieve method based on the MAX global variable we set.

The above is the detailed content of The smallest integer that divides every element in a given array > 1: using C++. For more information, please follow other related articles on the PHP Chinese website!