C++ 在[ 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进行范围查询，则第一段代码是最佳选择。

结论

在本教程中，我们实现了一个程序，用于找到与前m个元素都互质的前n个元素中的最大数，其中两个范围中均排除了1。互质数是指除了1之外没有任何公共因子的数。我们实现了一种改进版埃拉托斯特尼筛法，其时间复杂度为O(M*log(log(M)))，空间复杂度为O(N)，并且还有一种常数空间复杂度的方法。