nombor bebas padu kurang daripada n

Nombor tanpa faktor padu ialah nombor yang tidak mempunyai nombor padu sebagai faktor.

Faktor kubus ialah integer iaitu kubus dan membahagi nombor tanpa baki.

Sebagai contoh, 8 ialah faktor kubus 16 kerana 8 ialah faktor kubus 2 (2*2*2 = 8), dan baki pembahagian 8 dengan 16 ialah sifar.

Oleh itu, 8 atau 16 bukan nombor tanpa kubus.

Pernyataan Masalah

Cari semua nombor tanpa kubus kurang daripada nombor n yang diberi.

Contoh

Contoh

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.

Penjelasan

Penjelasan

Perhatikan bahawa 1, 8 dan 16 tiada dalam senarai. Kerana 1 dan 8 ialah nombor padu itu sendiri, dan 16 ialah gandaan 8.

Ada dua cara untuk menyelesaikan masalah ini.

Kaedah 1: Kaedah ganas

Kaedah brute force cracking adalah seperti berikut:

• Gelung semua nombor sehingga n.

• Untuk setiap nombor, lelaran melalui semua pembahaginya.

• Jika mana-mana faktor nombor ialah nombor padu, maka nombor itu bukan tanpa kubus.

• Jika tidak, jika tiada pembahagi nombor ini adalah kubik, maka ia adalah nombor tanpa kubus.

• Cetak nombor.

Contoh

Contoh

Program untuk pendekatan ini adalah seperti berikut −

Di bawah ialah program C++ untuk mencetak semua nombor tanpa kubus kurang daripada nombor n yang diberikan.

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

Output

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

Kaedah 2: Teknik Ayak Eratosthenes

Cara yang cekap untuk menyelesaikan masalah ini ialah konsep Saringan Eratosthenes.

Ia digunakan untuk mencari nombor perdana kurang daripada had yang diberikan. Di sini kami akan menapis nombor yang bukan nombor padu untuk mendapatkan penyelesaian kami.

Caranya adalah seperti berikut−

• Buat senarai boolean saiz n.

• Tandakan semua nombor sebagai benar. Ini bermakna pada masa ini kami telah melabelkan semua nombor sebagai tanpa kubus.

• Lintas semua kiub yang mungkin kurang daripada n.

• Melintasi semua gandaan nombor padu kurang daripada n.

• Tandakan semua gandaan ini dalam senarai sebagai palsu. Nombor ini tidak bebas kubus.

• Gelung senarai. Cetak nombor dalam senarai yang masih benar.

• Output akan merangkumi semua nombor tanpa kubus kurang daripada n.

Contoh

Contoh

Program untuk pendekatan ini adalah seperti berikut −

Berikut ialah program C++ yang menggunakan penapis Eratosthenes untuk mencetak semua nombor tanpa kubus kurang daripada nombor n yang diberikan.

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

Output

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

Artikel ini menyelesaikan masalah mencari nombor tanpa kubus kurang daripada n. Kami melihat dua kaedah: kaedah kekerasan dan kaedah cekap menggunakan penapis Eratosthenes.

Program C++ menyediakan pelaksanaan kedua-dua kaedah ini.

Atas ialah kandungan terperinci nombor bebas padu kurang daripada n. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!