使用 STL 基於因子數量排序

---

使用 STL 對向量進行排序非常簡單。我們可以使用著名的 sort() 函式來執行此任務。真正的挑戰是計算每個數字的因子數量。

因子是指完全整除另一個數字的數字，即餘數為零。

遍歷所有數字以計算因子可能是一種方法，但我們將在本文中嘗試最佳化並找到有效的解決方案。

問題陳述

根據每個數字的因子數量對給定陣列進行排序（升序）。因此，因子數量最少的數字應該位於開頭，因子數量最多的數字應該位於末尾。因子數量相同的數字應該與原始陣列中的順序相同。可以使用 STL 對陣列進行排序。

示例

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.

因此，根據因子對數字進行升序排序後，我們得到輸出：3 2 4 10 15 20。

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

解釋

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.

因此，根據因子對數字進行升序排序後，我們得到輸出：19 5 9 21 12。

方法

• 找到每個數字的因子數量。

• 建立一個儲存數字及其因子計數記錄的配對向量。

• 對向量進行排序並返回結果。

查詢數字的因子數量

暴力法

一個簡單的方法是從 1 到 n 遍歷所有數字，並找出它們是否整除 n。這樣，我們就可以計算每個數字的因子數量。

示例

下面是一個使用暴力法計算所有除數的 C++ 程式

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

輸出

The number of divisors of 55 is: 4

有效方法

一個數字的除數成對存在。

例如，12 的除數是 1、2、3、4、6、12。

但是，我們可以這樣視覺化它們：(1,12)、(2,6)、(3,4)。

因此，如果我們找到一個除數，我們也可以找到另一個除數，我們不需要遍歷到 n。

因此，有效的方法是隻遍歷到數字的平方根，然後成對計算除數。

示例

下面是一個計算數字的除數的 C++ 程式

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

輸出

The number of divisors of 55 is: 4

現在，我們可以遵循上面討論的方法的第 2 步和第 3 步。

基於因子數量列印排序向量的示例 C++ 程式

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

輸出

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

結論

在本文中，我們根據其因子的數量對整數向量進行了排序。

我們討論了一些示例，然後討論了方法。

此問題的核心是找到數字的除數個數。解決此問題可能有兩種方法：暴力法和有效方法。我們看到了這兩種方法，然後利用有效的方法編寫了最終程式。