Die kleinste ganze Zahl, die jedes Element in einem bestimmten Array teilt > 1: unter Verwendung von C++

In diesem Artikel erhalten wir ein Array von ganzen Zahlen und müssen die kleinste Zahl größer als 1 finden, die alle Elemente im Array teilt. Betrachten wir zum Beispiel ein Beispielarray [30, 90, 15, 45, 165].

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

Jetzt können wir den größten gemeinsamen Teiler (GCD) der Arrays ermitteln. Wenn das Ergebnis 1 ist, was bedeutet, dass nur 1 das gesamte Array teilen kann, können wir -1 oder „Nicht möglich“ zurückgeben. Wenn das Ergebnis eine ganze Zahl ist, dann teilt diese ganze Zahl das gesamte Array. Diese Ganzzahl ist jedoch möglicherweise nicht die kleinste Ganzzahl, die das gesamte Array teilt. Interessanterweise teilen Faktoren dieser ganzen Zahl auch das gesamte Array, was Sinn macht. Wenn wir also den kleinsten Faktor dieser ganzen Zahl (GCD) finden können, haben wir die kleinste ganze Zahl, die das gesamte Array teilt. Kurz gesagt, wir müssen den größten gemeinsamen Teiler (GCD) der Arrays finden und dann ist der kleinste Faktor unsere Antwort.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Der folgende C++-Code kann eine kleinste ganze Zahl größer als 1 finden, die alle Elemente im Array teilen kann. Dies kann erreicht werden, indem der größte gemeinsame Teiler einer Liste von Elementen ermittelt wird -

#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;
}

Ausgabe

3

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Bei vielen Abfragen wird die Suche nach den Primfaktoren einer Zahl wiederholt. Mit der Siebmethode können wir die Primfaktoren einer Zahl berechnen.

In C++ ist eine weitere Implementierungsmethode zum Finden der kleinsten Zahl größer als 1 wie folgt:

#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;
}

Ausgabe

3

Fazit

Wir haben die sqrt(n)-Methode verwendet, um den Mindestfaktor zu ermitteln. Dies kann optimiert werden, ich überlasse es Ihnen, es zu versuchen. Die Zeitkomplexität beträgt O(sqrt(n)). Bei der zweiten Methode entspricht die zeitliche Komplexität der der Siebmethode, also O(nlog(log(n))). Beachten Sie, dass wir die Obergrenze der Siebmethode basierend auf der von uns festgelegten globalen Variablen MAX ermitteln können.

Das obige ist der detaillierte Inhalt vonDie kleinste ganze Zahl, die jedes Element in einem bestimmten Array teilt > 1: unter Verwendung von C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!