Des chiffres nuisibles

Un nombre est considéré comme nuisible s'il s'agit d'un entier positif et que le nombre défini de chiffres dans son expansion binaire est un nombre premier. Le premier nombre nuisible est 3 car 3 = (11)₂. On peut voir que la représentation binaire de 3 a un nombre fixe de chiffres de 2, qui est un nombre premier.

Les 10 principaux nombres nuisibles sont 3, 5, 6, 7, 9, 10, 11, 12, 13, 14. Il est intéressant de noter que les puissances de 2 ne peuvent jamais être des nombres nuisibles car elles n’ont toujours qu’un seul bit défini. 1 n'est pas un nombre premier. D'un autre côté, tous les nombres qui peuvent être exprimés par 2ⁿ + 1, où n est n'importe quel nombre naturel, seront toujours de mauvais nombres car ils auront 2 bits définis, et nous savons que 2 est un nombre premier.

En gardant à l'esprit les propriétés de ces numéros nuisibles, l'article suivant explique comment vérifier si un numéro est nuisible.

Énoncé du problème

Cette question vise à vérifier si le nombre n donné est un nombre nuisible, c'est-à-dire qu'il s'agit d'un nombre positif avec un nombre premier de bits définis dans son développement binaire.

Exemple

Input: 37

Output: Pernicious

La traduction de

Explication

est :

Explication

37 = représentation binaire de 100101.

Définir le nombre de chiffres = 3

Puisque 3 est un nombre premier, 37 est un mauvais nombre.

Input: 22

Output: Pernicious

La traduction de

Explication

est :

Explication

22 = représentation binaire de 10110.

Définissez le nombre de chiffres = 3.

Puisque 3 est un nombre premier, 22 est un nombre vicieux.

Input: 71

Output: Not Pernicious

La traduction de

Explication

est :

Explication

La représentation binaire de 71 est 1000111.

Définissez le nombre de chiffres = 4.

Puisque 4 n'est pas un nombre premier, 71 n'est pas non plus un mauvais nombre.

Input: 64

Output: Not Pernicious

La traduction de

Explication

est :

Explication

La représentation binaire de 64 est 1000000.

Définissez le nombre de chiffres = 1.

Puisque 64 = 2⁶ c'est-à-dire que c'est une puissance de 2, il a 1 bit défini. Puisque 1 n’est pas un nombre premier, 64 n’est pas un nombre vicieux.

Solution

Nous devons savoir si le nombre de chiffres défini est un nombre premier afin de déterminer si un nombre est malveillant. La tâche principale à accomplir est de calculer le nombre défini de chiffres dans le développement binaire de ce nombre. La méthode suivante peut être utilisée pour calculer un nombre défini de chiffres, puis déterminer si le résultat est un nombre premier.

La méthode comprend les étapes suivantes -

• Parcourez tous les bits d'un nombre à l'aide des opérateurs de boucle et de décalage à droite.

• Si la valeur du bit est 1, le nombre de bits définis est augmenté de 1.

• Vérifiez si la valeur finale du décompte est un nombre premier.

• Afficher les réponses.

Algorithme

Fonction is_prime()

• si (n < 2)< 2)

erreur de retour

• pour (je de 2 à √a)

Si (a%i==0)

erreur de retour

• retour vrai

Fonction count_set_bits()

• Initialiser le compteur = 0

• quand (n > 0)

• si ((n&1)>0)

• compteur = compteur + 1

• n = n >> 1

• Compteur de retour

Fonction is_pernious()

• Initialiser le compteur

• Compteur = count_set_bits(n)

• if (is_prime(counter) == true)

retour vrai

• Autres

erreur de retour

Fonction principale()

• Initialiser n

• si (is_pernious())

cout <<"numéro nuisible"<<“Des chiffres nuisibles字”

• Autres

cout << « Numéro non préjudiciable »

• Impression

Exemple : programme C++

Le programme utilise la fonction

is_pernicious()

pour déterminer si un nombre est pernicieux. Il analyse les bits les moins significatifs à chaque itération de la boucle en décalant vers la droite la valeur de n à la fin de chaque itération dans la fonction

count_set_bits()

. Ensuite, il appelle la fonction

is_prime()

pour déterminer si le nombre de chiffres défini est un nombre premier.

#include <iostream>
using namespace std;
// this function counts the number of set bits by analyzing the rightmost bit using a while loop till n > 0.
// it performs logical & operation between 1 and n to determine if the rightmost bit is set or not.
// if it is set, count is incremented by 1
// right shift the value of n to make the bit left of the rightmost bit, the new rightmost bit.
int count_set_bits(int n){
   int count = 0;
   while (n > 0){
   
      // if the rightmost bit is 1: increment count
      if ((n & 1) > 0){
         count++;
      }
      
      // right shift the value of n to examine the next least significant bit
      n = n >> 1;
   }
   return count;
}

// this function determines if count of set bits in the given number is prime
bool is_prime(int count){
   if (count < 2)
   return false;
   for (int i = 2; i * i < count; i++){
      if (count % i == 0)
      return false;
   }
   return true;
}

// this functions states if count of set bits is prime -> pernicious
bool is_pernicious(int n){
   int count;
   count = count_set_bits(n);
   
   // if count is prime return true
   if (is_prime(count)){
      return true;
   }
   return false;
}

// main function
int main(){
   int n = 11;
   if (is_pernicious(n)){
      cout << n <<" is Pernicious Number";
   }
   else{
      cout << n << " is Non-Pernicious Number";
   }
   return 0;
}

Sortie

11 is Pernicious Number

Analyse espace-temps

Complexité temporelle : O(log(n) + sqrt(count)). Dans la fonction count_set_bits(), la boucle exécute log(n) fois pendant que nous analysons le nombre petit à petit. La fonction is_prime() prend un temps O(sqrt(count)) pour vérifier si count est premier. Les deux fonctions seront appelées une fois lors de l'exécution.

Complexité spatiale : O(1), puisqu'aucun espace auxiliaire n'est utilisé dans l'implémentation. Quelle que soit la taille du nombre saisi, l’algorithme utilise toujours une quantité d’espace constante.

Conclusion

Les mauvais nombres sont un concept mathématique intéressant et ils peuvent être identifiés facilement et efficacement en utilisant la méthode décrite ci-dessus. Cet article décrit également l'algorithme à utiliser, la solution du programme C++ et l'analyse de la complexité temporelle et spatiale.

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!