Finden Sie mit C++ Zahlen, die durch keine Zahl in einem Bereich teilbar sind

In diesem Artikel besprechen wir das Problem, Zahlen zwischen 1 und n (vorgegeben) zu finden, die nicht durch eine Zahl zwischen 2 und 10 teilbar sind. Lassen Sie uns dies anhand einiger Beispiele verstehen -

Input : num = 14
Output : 3
Explanation: There are three numbers, 1, 11, and 13, which are not divisible.

Input : num = 21
Output : 5
Explanation: There are five numbers 1, 11, 13, 17, and 19, which are not divisible.

Lösungsmöglichkeiten

Einfache Methode

Wenn wir jede Zahl von 1 bis num prüfen, ob sie durch eine beliebige Zahl zwischen 2 und 10 teilbar ist. Wenn nicht, erhöhen Sie die Anzahl. Diese Methode nimmt jedoch zu viel Zeit in Anspruch, wodurch die Zeitkomplexität zunimmt.

Effiziente Methode

Der beste Weg, den wir uns vorstellen können, besteht darin, zuerst die Zahlen von 1 bis num zu finden, die eine beliebige Zahl im Bereich [2, 10] sein können, und diese Zahl dann von num zu subtrahieren.

Also müssen wir zuerst alle Zahlen finden, die durch 2, 3, 4, 5, 10 teilbar sind. Aber Zahlen, die durch 4, 6, 8 und 10 teilbar sind, sind durch 2 teilbar, und Zahlen, die durch 3 teilbar sind, sind durch 6 und 9 teilbar.

Wir müssen alle Zahlen finden, die durch 2, 3 und 5 teilbar sind. , und 7. Wir können es nach dem Einschluss-Ausschluss-Prinzip berechnen.

Einschluss-Ausschluss-Prinzip

Es besagt, dass wir die Größe jedes einzelnen Satzes einbeziehen, die Größe paarweiser Schnittpunkte entfernen, die Größen aller Schnittpunkte der drei Sätze hinzufügen sollten und so weiter.

Die Formel zum Finden aller Zahlen lautet:

= NUM – X + Y – Z + A.

wo,

X = num divisible by 2, 3, 5, 7 ( [num / 2] + [num / 3] + [num / 5] + [num / 7] )

Y = num divisible by (2,3), (2, 5), (2, 7), (3, 5), (3, 5), (3, 7) and (5, 7) = ( [num / (2 * 3)] + [num / (2 * 5)] + [num / (2 * 7)] + [num / (3 * 5)] + num / (3 * 7)] + [num / (5 * 7)] ).

Z = num divisible by (2, 3, 5), (2, 3, 7), (2, 5, 7) and (3, 5, 7) = ( [num / (2 * 3 * 5)] + [num / (2 * 3 * 7)] + [num / (2 * 5 * 7)] + [num / (3 * 5 * 7)] )

A = num divisible by (2, 3, 5, 7) = ( [num / (2 * 3 * 5 * 7)] )

Beispiel

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 21, result;
   // applying formula from inclusion - exclusion principle
   // to find the count of numbers not divisible by any number from 2 to 10.
   result = n - n / 2 - n / 3 - n / 5 - n / 7
      + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35
      - n / 30 - n / 42 - n / 70 - n / 105 + n / 210;
   cout << "The count of numbers, not div by [2, 10] is: " << result;

   return 0;
}

Ausgabe

The count of numbers, not div by [2, 10] is: 5

Schlussfolgerung

In diesem Artikel haben wir Möglichkeiten besprochen, Zahlen zu finden, die nicht zwischen 2 und n teilbar sind. Um dieses Problem zu lösen, diskutieren wir das Inklusion-Ausschluss-Prinzip. Wir diskutieren auch C++-Programme, um diese Methode anzuwenden, um Ergebnisse in O(1)-Komplexität zu erhalten. Sie können dieses Programm in jeder anderen Sprache wie Java, C, Python usw. schreiben. Wir hoffen, dass dieser Artikel für Sie hilfreich war.

Das obige ist der detaillierte Inhalt vonFinden Sie mit C++ Zahlen, die durch keine Zahl in einem Bereich teilbar sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!