在 [2, 3, .. n] 中找到最大的数，并且该数与 [2, 3, .. m] 中的所有数互质。

---

互质数是指除了 1 之外没有其他公因数的数。我们将给出两个数字 n 和 m。我们必须找到 2 到 n（包含 2 和 n）范围内的最大数，该数与 2 到 m（包含 2 和 m）范围内的所有元素互质。如果给定范围内没有元素与第二个范围内的所有元素互质，则我们必须返回或打印 -1。我们将实现该方法、代码，并讨论程序的时间和空间复杂度。

输入

N = 20, M = 13 

输出

19

解释

我们总共有从 2 到 20 的元素。

所有偶数的最小公因数为 2，这意味着 2、4、6、8、…、20 已被排除。

所有能被 2 到 M 范围内的素数整除的元素都被排除。

剩下的元素只有 17 和 19。所以，19 是结果。

输入

N = 10, M = 7

输出

-1

解释

如前所述，2 到 10 范围内的所有偶数都被剔除。所有能被 3、5 和 7 整除的元素都被剔除。这意味着 2 到 10 范围内的任何元素都不与 2 到 7 范围内的元素互质。

方法 1

在这种方法中，我们将找到所有素数或不被小于等于 m 的任何素数整除且大于 m 的数。我们将在这里使用埃拉托色尼筛法的概念，但以修改后的方式来查找不被小于 m 的素数整除的数。

示例

#include <iostream>
using namespace std;
// function to check if any number in ranges are co-prime 
int find(int n, int m){
   // creating array to store the result 
   int arr[n+1] = {0}; 
   for(int i = 2; i <= m; i++){
      // if the current number is not prime then continue
      if(arr[i] == 1){
         continue;
      }
      // current number is prime number mark all the numbers that are not prime and divible by current number
      for(int j = 2; i*j <= n; j++){
         arr[i*j] = 1;
      }
   }
   // finding the last number which is greater than m and is prime
   for(int i = n; i>m; i--){
      if(arr[i] == 0){
         return i;
      }
   }
   return -1;
}
int main(){
   int n = 20;
   int m = 13;
   // calling the function to print the largest element 
   cout<<"The largest number that is co-prime is: " << find(n,m)<<endl;
   return 0;
}

输出

The largest number that is co-prime is: 19

时间和空间复杂度

上述代码的时间复杂度等价于埃拉托色尼筛法，即 O(M*log(log(M)))。

上述代码的空间复杂度为 O(N)，其中 N 是第一个范围。

方法 2

在这种方法中，我们将从 n 到 m（包含 n 但不包含 m）运行一个 for 循环，并且对于每个数字，我们将检查它们是否能被 2 到 m 的任何数字整除。

示例

#include <bits/stdc++.h>
using namespace std;
// function to check if the current number is divisible by any number in range 
bool isDivisble(int cur, int m){
   // getting square root of the current number 
   int sqr = sqrt(cur);
   // getting minimum of m and sqrt
   sqr = min(sqr,m);
   // checking divisblity 
   for(int i =2; i<= sqr; i++){
      if(cur%i == 0){
         return true;
      }
   }
   return false;
}
// function to check if any number in ranges are co-prime 
int find(int n, int m){
   // traversing over the given range from n to m 
   for(int i =n; i>m; i--){
      if(isDivisble(i, m)){
         continue;
      }
      else{
         return i;
      }
   }
   return -1;
}
int main(){
   int n = 10;
   int m = 7;
   // calling the function to print the largest element 
   cout<<"The largest number that is co-prime is: " << find(n,m)<<endl;
   return 0;
}

输出

The largest number that is co-prime is: -1

时间和空间复杂度

上述代码的时间复杂度等于 O(N*sqrt(N))，其中 sqrt(N) 是 N 的平方根。

上述代码的空间复杂度为 O(1)，因为我们在这里没有使用任何额外的空间。

从上面给出的两个程序来看，两者根据其自身的规格都很好。第一个代码花费的时间较少，但空间复杂度较高，而第二个代码花费的时间更多，但空间复杂度较低。

如果 N 的值很高，则第二个代码是最好的，否则第一个代码是最好的。

如果对于固定的 m 对 n 进行范围查询，则第一个代码是最好的。

结论

在本教程中，我们实现了一个程序来查找第一个 n 个元素中最大的数，该数与前 m 个元素中的所有元素互质，其中 1 在两个范围内都不包含。互质数是指除了 1 之外没有其他公因数的数。我们实现了一种方法，它是埃拉托色尼筛法的修改版本，时间复杂度为 O(M*log(log(M)))，空间复杂度为 O(N)，以及另一种具有常数空间复杂度的方案。