Sort by number of factors using STL

Sorting vectors using STL is a piece of cake. We can use the famous sort() function to accomplish this task. The real challenge is counting the number of factors for each number.

A factor is a number that can completely divide another number, that is, the remainder is zero.

Looping through all the numbers to calculate the factors might be one way to do it, but we will try to optimize and arrive at an efficient solution in this article.

Problem Statement

Sort the given array in ascending order based on the number of factors for each number. Therefore, the number with the smallest number of factors should be at the beginning and the number with the largest number of factors should be at the end. Numbers with the same number of factors should be arranged in the order of the original array. Arrays can be sorted using STL.

The Chinese translation of

Example

is:

Example

Input − Array a = [15,2,20,3,10,4]
Output − 3 2 4 10 15 20
pre class="just-code notranslate 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.

So, after sorting the numbers in ascending order according to their factors, we get the output: 3 2 4 10 15 20.

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

Explanation

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.

So, after sorting the numbers in ascending order according to their factors, we get the output: 19 5 9 21 12

method

• Find the number of factors of each number.

• Create a vector that stores pairs of numbers and their factor counts.

• Sort the vector and return the result.

Find the number of factors of a number

The Chinese translation of

Brute Force

is:

BRute Force

A naive approach would be to loop through all the numbers from 1 to n and find out if they divide n. This way, we can calculate the number of factors for each number.

The Chinese translation of

Example

is:

Example

The following is a C program that uses brute force to calculate all divisors of a number

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

Output

The number of divisors of 55 is: 4

Efficient method

The factors of a number exist in pairs.

For example, the divisors of 12 are 1, 2, 3, 4, 6, 12.

However, we can visualize them like this: (1,12), (2,6), (3,4).

So if we find a divisor, we can also find another divisor without traversing to n.

Therefore, an efficient method is to traverse only to the square root of the number and then calculate the divisors in pairs.

The Chinese translation of

Example

is:

Example

The following is a C program for calculating the divisor of a number

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

Output

The number of divisors of 55 is: 4

Now, we can follow the second and third steps of the method discussed above.

Example C program to print sorted vectors based on number of factors

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

Output

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

in conclusion

In this article, we sorted a vector based on the number of factors of integers.

We discussed some examples and then talked about methods.

The core of this problem is to find the number of divisors of a number. There are two ways to solve this problem: brute force method and efficient method. We looked at both approaches and then used the efficient approach to write the final program.

The above is the detailed content of Sort by number of factors using STL. For more information, please follow other related articles on the PHP Chinese website!