在 [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)，以及另一種具有常數空間複雜度的方案。