Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Banananjoyer's blog

By Banananjoyer, history, 2 months ago, In English

I recently learnt about the algorithm to print out factors of a number in pairs. This is done by iterating with counter i from 1 to $$$\sqrt{n}$$$, printing i and $$$\frac{n}{i}$$$ if n % i == 0. As an exercise, I extended this algorithm so instead of pairs, it can be triples, quadruples or any integer k >= 2. This means printing out every multiset of length k such that the products of the elements is n. It iterates to the $$$\sqrt[k]{n}$$$. It calls itself recursively, reducing k by 1 until k = 2. It then does the same pair finding as before. So factuples_algorithm(20, 3) will print out the factor triples {1, 1, 20}, {1, 2, 10}, {1, 4, 5}, {2, 2, 5}.

The algorithm I wrote:

#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>

void factuples_algorithm(int n, int k, std::vector<int> output_stack = {}, int loop_start = 1) {
	for (int i = loop_start; std::nearbyint(std::pow(i, k)) <= n; i++) {
	  	if (n % i == 0 and k >= 2) {
			output_stack.push_back(i);
			if(k >= 3) {
				factuples_algorithm(n/i, k - 1, output_stack, i); //call recursively until k = 2
				output_stack.pop_back();
			} else {
				output_stack.push_back(n/i);
				for(int j = 0; j < output_stack.size(); j++) {
					std::cout << output_stack[j] << " ";
				}
				std::cout << '\n';
				output_stack.pop_back();
				output_stack.pop_back(); //remove ending pair
			}
		}
	}
}

int main() {
	int n{}; std::cin >> n;
	int k{}; std::cin >> k;
	factuples_algorithm(n, k);
	return 0;
}

My question is on the time complexity of this algorithm. If k = 4 for example, it is algorithm of $$$\sqrt[4]{n}$$$ complexity with $$$\sqrt[3]{n}$$$ inside with $$$\sqrt{n}$$$ inside. So is the time complexity O(n^(1/2 + 1/3 + ... 1/k)), which becomes O(n^(log(k)) from the harmonic series? Or am I wrong?

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it