Table des matières
Façons de résoudre
Méthode simple
Méthode efficace
Principe d'inclusion-exclusion
Exemple
Sortie
Conclusion
Maison développement back-end C++ Rechercher des nombres qui ne sont divisibles par aucun nombre dans une plage, à l'aide de C++

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

Sep 13, 2023 pm 09:21 PM
数字 整除 范围

Rechercher des nombres qui ne sont divisibles par aucun nombre dans une plage, à laide 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.
Copier après la connexion

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.
Copier après la connexion

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)] )
Copier après la connexion

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;
}
Copier après la connexion

Sortie

The count of numbers, not div by [2, 10] is: 5
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

Repo: Comment relancer ses coéquipiers
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
1 Il y a quelques mois By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
4 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Explication détaillée des opérations de division entière et des méthodes de calcul du reste en langage Go Explication détaillée des opérations de division entière et des méthodes de calcul du reste en langage Go Mar 23, 2024 pm 06:00 PM

Explication détaillée des opérations de division entière et des méthodes de calcul de reste en langage Go. En langage Go, les opérations de division entière et les calculs de reste sont des opérations mathématiques courantes. Cet article explique comment effectuer des opérations de division d'entiers et des calculs de reste dans le langage Go, et fournit des exemples de code spécifiques. Opération de division entière Dans le langage Go, le symbole / est utilisé pour l'opération de division entière. L'opération de division entière consiste à prendre le quotient de la division de deux nombres. Le résultat est la partie entière, c'est-à-dire que la partie décimale est ignorée et aucune opération d'arrondi n'est effectuée. Les opérations de division entière sont souvent utilisées pour calculer le quotient entier après division. Exemple de code : package

iOS 17 : Comment changer le style d'horloge de l'iPhone en mode veille iOS 17 : Comment changer le style d'horloge de l'iPhone en mode veille Sep 10, 2023 pm 09:21 PM

La veille est un mode d'écran de verrouillage qui s'active lorsque l'iPhone est branché sur le chargeur et orienté en orientation horizontale (ou paysage). Il se compose de trois écrans différents, dont l'un affiche l'heure en plein écran. Lisez la suite pour savoir comment changer le style de votre horloge. Le troisième écran de StandBy affiche les heures et les dates dans différents thèmes que vous pouvez faire glisser verticalement. Certains thèmes affichent également des informations supplémentaires, comme la température ou la prochaine alarme. Si vous maintenez une horloge enfoncée, vous pouvez basculer entre différents thèmes, notamment numérique, analogique, mondial, solaire et flottant. Float affiche l'heure dans de grands nombres de bulles dans des couleurs personnalisables, Solar a une police plus standard avec un motif d'éruption solaire dans différentes couleurs et World affiche le monde en mettant en surbrillance

Générer des nombres et des chaînes aléatoires en JavaScript Générer des nombres et des chaînes aléatoires en JavaScript Sep 02, 2023 am 08:57 AM

La possibilité de générer des nombres aléatoires ou des chaînes alphanumériques s'avère utile dans de nombreuses situations. Vous pouvez l'utiliser pour faire apparaître des ennemis ou de la nourriture à différents endroits du jeu. Vous pouvez également l'utiliser pour suggérer des mots de passe aléatoires aux utilisateurs ou créer des noms de fichiers pour enregistrer des fichiers. J'ai écrit un tutoriel sur la façon de générer des chaînes alphanumériques aléatoires en PHP. J'ai dit au début de cet article que peu d'événements sont véritablement aléatoires, et il en va de même pour la génération de nombres aléatoires ou de chaînes. Dans ce tutoriel, je vais vous montrer comment générer une chaîne alphanumérique pseudo-aléatoire en JavaScript. Générer des nombres aléatoires en JavaScript Commençons par générer des nombres aléatoires. La première méthode qui me vient à l’esprit est Math.random(), qui renvoie un float

Utilisez la fonction StringBuilder.replace() de Java pour remplacer une plage de caractères spécifiée Utilisez la fonction StringBuilder.replace() de Java pour remplacer une plage de caractères spécifiée Jul 24, 2023 pm 06:12 PM

Utilisez la fonction StringBuilder.replace() de Java pour remplacer une plage de caractères spécifiée. En Java, la classe StringBuilder fournit la méthode replace(), qui peut être utilisée pour remplacer une plage de caractères spécifiée dans une chaîne. La syntaxe de cette méthode est la suivante : publicStringBuilderreplace(intstart,intend,Stringstr) La méthode ci-dessus est utilisée pour remplacer l'étoile d'index de

Programme C++ pour arrondir un nombre à n décimales Programme C++ pour arrondir un nombre à n décimales Sep 12, 2023 pm 05:13 PM

Représenter des nombres en sortie est une tâche intéressante et importante lors de l’écriture d’un programme dans n’importe quel langage. Pour les types entiers (données de type court, long ou moyen), il est facile de représenter des nombres en sortie. Pour les nombres à virgule flottante (de type flottant ou double), nous devons parfois les arrondir à un nombre spécifique de décimales. Par exemple, si nous voulons représenter 52,24568 sous forme de trois décimales, un prétraitement est nécessaire. Dans cet article, nous présenterons plusieurs techniques pour représenter les nombres à virgule flottante avec un nombre spécifique de décimales par arrondi. Parmi les différentes approches, il est important d'utiliser une chaîne de format de type C, d'utiliser l'argument de précision et d'utiliser la fonction round() de la bibliothèque mathématique. Regardons-les un par un. avec

Rechercher des nombres qui ne sont divisibles par aucun nombre dans une plage, à l'aide de C++ Rechercher des nombres qui ne sont divisibles par aucun nombre dans une plage, à l'aide de C++ Sep 13, 2023 pm 09:21 PM

Dans cet article, nous aborderons le problème de la recherche de nombres compris entre 1 et n (donnés) qui ne sont divisibles par aucun nombre compris entre 2 et 10. Comprenons cela avec quelques exemples - Entrée : num = 14 Sortie : 3 Explication : Il y a trois nombres, 1, 11 et 13, qui ne sont pas divisibles. Entrée : num = 21 Sortie : 5 Explication : Il y a cinq nombres 1, 11, 13, 17 et 19, qui ne sont pas divisibles. Méthode simple résolue si.

Nombres en Java (avec préfixe 0 et chaînes) Nombres en Java (avec préfixe 0 et chaînes) Aug 29, 2023 pm 01:45 PM

Nombres en Java Il est important de comprendre que la classe nombre n'est pas une classe tangible mais une classe abstraite. À l’intérieur, nous avons un ensemble de classes wrapper qui définissent ses fonctionnalités. Ces classes wrapper incluent Integer, Byte, Double, Short, Float et Long. Vous remarquerez peut-être qu'il s'agit des mêmes types de données de base dont nous avons parlé plus tôt, mais ils sont représentés comme des classes distinctes avec des noms en majuscules pour se conformer à la convention de dénomination des classes. Le compilateur convertit automatiquement les types de données primitifs en objets et vice versa selon les besoins d'une fonction ou d'une portée de programme particulière, et les classes numériques font partie du package java.lang. Ce processus est appelé autoboxing et unboxing. En saisissant la nature abstraite des classes numériques et de leurs classes wrapper correspondantes, nous pouvons

Utilisez C++ pour écrire du code afin de trouver le Nième nombre non carré Utilisez C++ pour écrire du code afin de trouver le Nième nombre non carré Aug 30, 2023 pm 10:41 PM

Nous connaissons tous des nombres qui ne sont le carré d’aucun nombre, comme 2, 3, 5, 7, 8, etc. Il existe N nombres non carrés et il est impossible de connaître tous les nombres. Ainsi, dans cet article, nous expliquerons tout sur les nombres sans carrés ou non carrés et les moyens de trouver le Nième nombre non carré en C++. Nième nombre non carré Si un nombre est le carré d'un entier, alors ce nombre est appelé un carré parfait. Quelques exemples de nombres carrés parfaits sont -1iscarréde14iscarréde29iscarréde316iscarréde425iscarréde5 Si un nombre n'est le carré d'aucun entier, alors le nombre est appelé non carré. Par exemple, les 15 premiers nombres non carrés sont -2,3,5,6,

See all articles