Integer terkecil yang membahagikan setiap elemen dalam tatasusunan tertentu > 1: menggunakan C++

Dalam artikel ini, kita diberikan tatasusunan integer dan kita perlu mencari nombor terkecil lebih besar daripada 1 yang membahagikan semua elemen dalam tatasusunan. Sebagai contoh, mari kita pertimbangkan tatasusunan contoh [30, 90, 15, 45, 165].

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

Kini kita boleh mencari Pembahagi Sepunya Terhebat (GCD) tatasusunan. Jika hasilnya ialah 1, yang bermaksud hanya 1 yang boleh membahagikan keseluruhan tatasusunan, kita boleh mengembalikan -1 atau "Tidak mungkin." Jika hasilnya ialah integer, maka integer ini membahagikan keseluruhan tatasusunan. Walau bagaimanapun, integer ini mungkin bukan integer terkecil yang membahagikan keseluruhan tatasusunan. Menariknya, faktor integer ini juga membahagikan keseluruhan tatasusunan, yang masuk akal. Jadi, jika kita boleh mencari faktor terkecil integer ini (GCD), kita mempunyai integer terkecil yang membahagikan keseluruhan tatasusunan. Jadi, secara ringkasnya, kita perlu mencari Pembahagi Sepunya Terbesar (GCD) tatasusunan dan kemudian faktor terkecil ialah jawapan kita.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Kod C++ berikut boleh mencari integer terkecil lebih besar daripada 1 yang boleh membahagikan semua elemen dalam tatasusunan. Ini boleh dicapai dengan mencari pembahagi sepunya terbesar bagi senarai elemen -

#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

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Jika terdapat banyak pertanyaan, mencari faktor perdana bagi sesuatu nombor akan diulang. Dengan menggunakan kaedah ayak, kita boleh mengira faktor perdana sesuatu nombor.

Dalam C++, kaedah pelaksanaan lain untuk mencari nombor terkecil lebih besar daripada 1 adalah seperti berikut:

#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

Kesimpulan

Kami menggunakan kaedah sqrt(n) untuk mendapatkan faktor minimum. Ini boleh dioptimumkan, saya serahkan kepada anda untuk mencuba. Kerumitan masa ialah O(sqrt(n)). Dalam kaedah kedua, kerumitan masa ialah kaedah penapis, iaitu O(nlog(log(n))). Ambil perhatian bahawa kita boleh mencari had atas kaedah ayak berdasarkan pembolehubah global MAX yang kita tetapkan.

Atas ialah kandungan terperinci Integer terkecil yang membahagikan setiap elemen dalam tatasusunan tertentu > 1: menggunakan C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!