Rechercher des nombres qui ne sont divisibles par aucun nombre dans une plage, à l'aide de C++

Dans cet article, nous aborderons le problème de trouver des nombres entre 1 et n (donnés) qui ne sont divisibles par aucun nombre entre 2 et 10. Comprenons cela avec quelques exemples -

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.

Façons de résoudre

Méthode simple

Si nous vérifions chaque nombre de 1 à num, s'il est divisible par un nombre compris entre 2 et 10. Sinon, incrémentez le décompte. Mais cette méthode prend trop de temps, augmentant ainsi la complexité temporelle.

Méthode efficace

La meilleure à laquelle nous puissions penser est de trouver d'abord les nombres de 1 à num, qui peuvent être n'importe quel nombre compris dans la plage [2, 10], puis de soustraire ce nombre de num.

Donc d'abord, nous devons trouver tous les nombres divisibles par 2, 3, 4, 5,10. Mais les nombres divisibles par 4, 6, 8 et 10 sont divisibles par 2, et les nombres divisibles par 3 sont divisibles par 6 et 9.

Nous devons trouver tous les nombres divisibles par 2, 3 et 5. , et 7. Nous pouvons le calculer sur la base du principe d’inclusion-exclusion.

Principe d'inclusion-exclusion

Il stipule que nous devons inclure la taille de chaque ensemble individuel, que vous devez supprimer la taille des intersections par paires, ajouter les tailles de toutes les intersections des trois ensembles, et ainsi de suite.

La formule pour trouver tous les nombres est

= NUM – X + Y – Z + A.

où,

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)] )

Exemple

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

Sortie

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

Conclusion

Dans cet article, nous avons discuté des façons de trouver des nombres qui ne sont pas divisibles entre 2 et n. Pour résoudre ce problème, nous discutons du principe d’inclusion-exclusion. Nous discutons également des programmes C++ permettant d'appliquer cette méthode pour obtenir des résultats en complexité O(1). Vous pouvez écrire ce programme dans n'importe quel autre langage comme Java, C, Python, etc. Nous espérons que cet article vous a été utile.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!