nombre cubique libre inférieur à n

Les nombres sans facteurs cubiques sont les nombres qui n'ont pas de nombres cubes comme facteurs.

Un facteur cubique est un entier qui est un cube et divise le nombre sans reste.

Par exemple, 8 est un facteur cubique de 16 car 8 est un facteur cubique de 2 (2*2*2 = 8), et le reste de la division de 8 par 16 est nul.

Par conséquent, ni 8 ni 16 ne sont des nombres sans cube.

Énoncé du problème

Trouvez tous les nombres sans cube inférieurs au nombre n donné.

Exemple

Exemple

Let's understand the problem with an example.
Let n = 15,
Thus, we have to find all the numbers less than 15 that are cube-free.
The solution will be:  2,3,4,5,6,7,9,10,11,12,13,14.
For another example,
Let n = 20.
The numbers are 2,3,4,5,6,7,9,10,11,12,13,14,15,17,18,19.

Explication

Explication

Notez que 1, 8 et 16 ne sont pas dans la liste. Parce que 1 et 8 sont eux-mêmes des nombres cubes et que 16 est un multiple de 8.

Il existe deux façons de résoudre ce problème.

Méthode 1 : Méthode violente

La méthode de cracking par force brute est la suivante :

• Parcourez tous les nombres jusqu'à n.

• Pour chaque nombre, parcourez tous ses diviseurs.

• Si l'un des facteurs d'un nombre est un nombre cubique, alors le nombre n'est pas sans cube.

• Sinon, si aucun des diviseurs de ces nombres n'est cubique, alors c'est un nombre sans cube.

• Imprimez les numéros.

Exemple

Exemple

Le programme de cette approche est le suivant −

Vous trouverez ci-dessous un programme C++ pour imprimer tous les nombres sans cube inférieurs à un nombre n donné.

#include<iostream>
using namespace std;
// This function returns true if the number is cube free.
// Else it returns false.
bool is_cube_free(int n){
   if(n==1){
      return false;
   }
   //Traverse through all the cubes lesser than n
   for(int i=2;i*i*i<=n ;i++){
      //If a cube divides n completely, then return false.
      if(n%(i*i*i) == 0){
         return false;
      }
   }
   return true;
}
int main(){
   int n = 17;
   cout<<"The cube free numbers smaller than 17 are:"<<endl;
   //Traverse all the numbers less than n
   for(int i=1;i<n;i++){
      //If the number is cube free, then print it.
      if(is_cube_free(i)){
         cout<<i<<" ";
      }
   }
}

Sortie

The cube free numbers smaller than 17 are:
2 3 4 5 6 7 9 10 11 12 13 14 15

Méthode 2 : Technique du tamis d'Eratosthène

Un moyen efficace de résoudre ce problème serait le concept du Tamis d'Ératosthène.

Il est utilisé pour trouver des nombres premiers inférieurs à une limite donnée. Ici, nous allons filtrer les nombres qui ne sont pas des nombres cubes pour obtenir notre solution.

La méthode est la suivante−

• Créez une liste booléenne de taille n.

• Marquez tous les nombres comme vrais. Cela signifie que nous avons actuellement étiqueté tous les nombres comme étant sans cube.

• Parcourez tous les cubes possibles inférieurs à n.

• Parcourez tous les multiples de nombres cubes inférieurs à n.

• Marquez tous ces multiples dans la liste comme faux. Ces nombres ne sont pas exempts de cubes.

• Parcourez la liste. Imprimez les nombres de la liste qui sont toujours vrais.

• La sortie inclura tous les nombres sans cube inférieurs à n.

Exemple

Exemple

Le programme de cette approche est le suivant −

Vous trouverez ci-dessous un programme C++ qui utilise le tamis d'Eratosthène pour imprimer tous les nombres sans cube inférieurs à un nombre n donné.

#include<iostream>
#include<vector>
using namespace std;

//Find which numbers are cube free and mark others as false in the vector.
void find_cube_free(vector<bool>&v, int n){
   //Traverse through all the numbers whose cubes are lesser than n
   for(int i=2;i*i*i<n;i++){
      
      //If i isn't cube free, it's multiples would have been marked false too
      if(v[i]==true){
         //Mark all the multiples of the cube of i as not cube free.
         for(int j=1;i*i*i*j<n;j++){
            v[i*i*i*j] = false;
         }
      }
   }
}
int main(){
   int n = 15;
   
   //Vector to store which numbers are cube free
   //Initially, we set all the numbers as cube free
   vector<bool>v(n,true);
   find_cube_free(v,n);
   cout<<"The cube free numbers smaller than are:"<<endl;
   
   //Traverse the vector and print the cube free numbers
   for(int i=2;i<n;i++){
      if(v[i]==true){
         cout<<i<<" ";
      }
   }
}

Sortie

The cube free numbers smaller than are:
2 3 4 5 6 7 9 10 11 12 13 14

Cet article résout le problème de la recherche de nombres sans cube inférieurs à n. Nous avons vu deux méthodes : une méthode par force brute et une méthode efficace utilisant le tamis d'Eratosthène.

Le programme C++ permet l'implémentation de ces deux méthodes.

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!