C++ 按照因数的数量使用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

结论

在本文中，我们基于一个整数向量的因子数量对其进行了排序。

我们讨论了几个示例，然后讨论了解决方法。

这个问题的核心是找到一个数的除数的数量。解决这个问题有两种方法：蛮力法和高效方法。我们展示了这两种方法，并且利用了高效方法来编写最终的程序。