kubische freie Zahl kleiner als n

Zahlen ohne Kubikfaktoren sind Zahlen, die keine Kubikzahlen als Faktoren haben.

Ein Kubikfaktor ist eine ganze Zahl, die eine Kubikzahl ist und die Zahl ohne Rest dividiert.

Zum Beispiel ist 8 ein Kubikfaktor von 16, weil 8 ein Kubikfaktor von 2 ist (2*2*2 = 8) und der Rest der Division von 8 durch 16 Null ist.

Deshalb sind weder 8 noch 16 würfellose Zahlen.

Problemstellung

Finden Sie alle würfellosen Zahlen, die kleiner als die angegebene Zahl n sind.

Beispiel

wird übersetzt als:

Beispiel

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.

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Beachten Sie, dass 1, 8 und 16 nicht in der Liste enthalten sind. Weil 1 und 8 selbst Kubikzahlen sind und 16 ein Vielfaches von 8 ist.

Es gibt zwei Möglichkeiten, dieses Problem zu lösen.

Methode 1: Gewalttätige Methode

Die Methode zum Brute-Force-Cracken ist wie folgt:

• Durchlaufe alle Zahlen bis n.

• Iterieren Sie für jede Zahl alle ihre Teiler.

• Wenn ein Faktor einer Zahl eine kubische Zahl ist, dann ist die Zahl nicht kubisch.

• Andernfalls, wenn keiner der Teiler dieser Zahlen kubisch ist, handelt es sich um eine würfellose Zahl.

• Zahlen drucken.

Beispiel

wird übersetzt als:

Beispiel

Das Programm für diesen Ansatz lautet wie folgt: −

Unten ist ein C++-Programm zum Drucken aller würfellosen Zahlen kleiner als eine gegebene Zahl n.

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

Ausgabe

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

Methode 2: Sieb der Eratosthenes-Technik

Ein effizienter Weg, dieses Problem zu lösen, wäre das Konzept des Siebes des Eratosthenes.

Es wird verwendet, um Primzahlen zu finden, die kleiner als ein bestimmter Grenzwert sind. Hier werden wir die Zahlen herausfiltern, die keine kubischen Zahlen sind, um unsere Lösung zu erhalten.

Die Methode ist wie folgt:

• Erstellen Sie eine boolesche Liste der Größe n.

• Markieren Sie alle Zahlen als wahr. Das bedeutet, dass wir derzeit alle Zahlen als würfellos gekennzeichnet haben.

• Durchlaufe alle möglichen Würfel kleiner als n.

• Durchlaufen Sie alle Vielfachen kubischer Zahlen kleiner als n.

• Markieren Sie alle diese Vielfachen in der Liste als falsch. Diese Zahlen sind nicht würfelfrei.

• Durchlaufen Sie die Liste. Geben Sie die Zahlen in der Liste aus, die noch wahr sind.

• Die Ausgabe umfasst alle würfellosen Zahlen kleiner als n.

Beispiel

wird übersetzt als:

Beispiel

Das Programm für diesen Ansatz lautet wie folgt: −

Unten ist ein C++-Programm, das das Sieb von Eratosthenes verwendet, um alle würfellosen Zahlen kleiner als eine gegebene Zahl n auszugeben.

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

Ausgabe

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

Dieser Artikel löst das Problem, würfellose Zahlen kleiner als n zu finden. Wir haben zwei Methoden gesehen: eine Brute-Force-Methode und eine effiziente Methode mit dem Sieb des Eratosthenes.

C++-Programm bietet die Implementierung dieser beiden Methoden.

Das obige ist der detaillierte Inhalt vonkubische freie Zahl kleiner als n. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!