Trier par nombre de facteurs à l'aide de STL

Le tri des vecteurs à l'aide de STL est un jeu d'enfant. Nous pouvons utiliser la célèbre fonction sort() pour accomplir cette tâche. Le véritable défi consiste à compter le nombre de facteurs pour chaque nombre.

Un facteur est un nombre qui divise complètement un autre nombre, c'est-à-dire avec un reste nul.

Parcourir tous les nombres pour calculer les facteurs pourrait être une voie à suivre, mais nous essaierons d'optimiser et d'arriver à une solution efficace dans cet article.

Énoncé du problème

Triez le tableau donné par ordre croissant en fonction du nombre de facteurs de chaque nombre. Par conséquent, le nombre avec le plus petit nombre de facteurs doit être au début et celui avec le plus grand nombre de facteurs doit être à la fin. Les nombres avec le même nombre de facteurs doivent être disposés dans l’ordre du tableau d’origine. Les tableaux peuvent être triés à l'aide de STL.

La traduction chinoise de

Exemple

est :

Exemple

Input − Array a = [15,2,20,3,10,4]
Output − 3 2 4 10 15 20
pre class="just-code notranslate language-cpp" data-lang="cpp">
The number of factors of 15 − 4.
The number of factors of 2 −  2.
The number of factors of 20 − 6.
The number of factors of 3 −  2.
The number of factors of 10 − 4.
The number of factors of 4 −  3.

Ainsi, après avoir trié les nombres par ordre croissant en fonction de leurs facteurs, nous obtenons le résultat : 3 2 4 10 15 20.

Input − Array a = [5,9,12,19,21]
Output − 19 5 9 21 12

Explication

The number of factors of 5 −  3.
The number of factors of 9 −  3.
The number of factors of 12 − 4.
The number of factors of 19 − 2.
The number of factors of 21 − 4.

Ainsi, après avoir trié les nombres par ordre croissant en fonction de leurs facteurs, nous obtenons le résultat : 19 5 9 21 12

Méthode

• Trouvez le nombre de facteurs de chaque nombre.

• Créez un vecteur qui stocke des paires de nombres et leurs nombres de facteurs.

• Triez le vecteur et renvoyez le résultat.

Trouver le nombre de facteurs d'un nombre

La traduction chinoise de

Brute Force

est :

Brute Force

Une approche naïve serait de parcourir tous les nombres de 1 à n et de découvrir s'ils divisent n. De cette façon, nous pouvons calculer le nombre de facteurs pour chaque nombre.

La traduction chinoise de

Exemple

est :

Exemple

Ce qui suit est un programme C++ qui utilise la force brute pour calculer tous les diviseurs d'un nombre

#include <bits/stdc++.h>
using namespace std;
// function to count the divisors
int countDivisors(int n){
   int count = 0;
	for (int i = 1; i <= n; i++){
	   if (n % i == 0)
		   count++;
	} 
   return count;
}

int main(){
   int n = 55;
   //Function call
   int ans = countDivisors(n);
	cout <<"The number of divisors of 55 is: "<<ans<<endl;
	return 0;
}

Sortie

The number of divisors of 55 is: 4

Méthode efficace

Les facteurs d'un nombre existent par paires.

Par exemple, les diviseurs de 12 sont 1, 2, 3, 4, 6, 12.

Cependant, on peut les visualiser ainsi : (1,12), (2,6), (3,4).

Donc, si nous trouvons un diviseur, nous pouvons également trouver un autre diviseur sans passer par n.

Le moyen efficace consiste donc simplement à parcourir jusqu'à la racine carrée du nombre, puis à calculer les diviseurs par paires.

La traduction chinoise de

Exemple

est :

Exemple

Ce qui suit est un programme C++ pour calculer le diviseur d'un nombre

#include <bits/stdc++.h>
using namespace std;
// Function to count the divisors of a number
int countDivisors(int n){
   int count = 0;
	for (int i=1; i<=sqrt(n); i++){
		if (n%i == 0){
			// If divisors are equal, count only one
			if (n/i == i)
				count++;
			else // Otherwise count both
				count += 2;
		}
	}
	return count;
}

int main(){
   int n = 55;
   int ans = countDivisors(n);
   cout <<"The number of divisors of 55 is: "<<ans<<endl;
   return 0;
}

Sortie

The number of divisors of 55 is: 4

Maintenant, nous pouvons suivre les deuxième et troisième étapes de la méthode évoquée ci-dessus.

Exemple de programme C++ pour imprimer des vecteurs triés en fonction du nombre de facteurs

#include <bits/stdc++.h>
using namespace std;
// Function to count the divisors of a number
int countDivisors(int n){
	int count = 0;
	for (int i=1; i<=sqrt(n); i++){
		if (n%i == 0){
			// If divisors are equal, count only one
			if (n/i == i)
				count++;
			else // Otherwise count both
				count += 2;
		}
	}
	return count;
}
int main(){
   int n = 5;
   vector<int>vec;
   //Inserting input
   vec.push_back(5);
   vec.push_back(14);
   vec.push_back(18);
   vec.push_back(9);
   vec.push_back(10);
   //Vector of pairs to store the number and its factor count
   vector<pair<int,int>>count_data(n);
   for(int i=0;i<n;i++){
      //Storing the data in the vector
      count_data[i] = {countDivisors(vec[i]), vec[i]};
   }
   //Sort the vector according to the number of factors
   sort(count_data.begin(),count_data.end());
   //Printing the result
   cout<<"The sorted vector based on the number of factors is: \n";
   for(int i=0;i<n;i++){
      cout<<count_data[i].second<<" ";
   }
   return 0;
}

Sortie

The sorted vector based on the number of factors is: 
5 9 10 14 18 

Conclusion

Dans cet article, nous avons trié un vecteur en fonction du nombre de facteurs d'entiers.

Nous avons discuté de quelques exemples puis parlé des méthodes.

Le cœur de ce problème est de trouver le nombre de diviseurs d'un nombre. Il existe deux manières de résoudre ce problème : la méthode par force brute et la méthode efficace. Nous avons examiné les deux approches, puis avons utilisé l'approche efficace pour rédiger le programme final.

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!