1

I am given the prime factorization of a number p1^x1 * p2^x2 * .... in a map. I need to iterate through all its factors, prime as well as composite. I managed to write a solution using recursion.

#include <iostream>
#include <map>
#include <cstdlib>

using namespace std;

struct PROBLEM {

    int mx = 400;
    map<int, int> mp = {{2, 2}, {3, 1},  {5, 1}, {7, 2}};
    int lastPrimeFactor = 7;
    int num = 1;

    auto solve() {
        rec(2, 0);
        return 0;
    }

    int next_prime_factor(int p) {
        return (p == 2) ? 3 : (p == 3) ? 5 : (p == 5) ? 7 : -1;
    }

    void rec(int prime, int power) {

        if (mx == 0) {
            cout << "Infinite recursion\n\n";
            exit(0);
        } else --mx;

        if (prime == lastPrimeFactor && power > mp[prime]) {
            return;
        }

        if (power < mp[prime]) {
            num *= prime;
            cout << num << endl;
            rec(prime,  power + 1);
            num /= prime;
        }

        if (prime != lastPrimeFactor) {
            rec(next_prime_factor(prime),  0);
        }

    }

};


int main() {
    PROBLEM().solve();
    return 0;
}

Questions:

1) Is there any faster way to generate these factors?

2) If possible, can I replace the recursion by a while loop?

xylon97
  • 153
  • 5
  • cf. http://stackoverflow.com/questions/29992904/enumerate-factors-of-a-number-directly-in-ascending-order-without-sorting/30181351#30181351 – Will Ness Aug 22 '16 at 20:45

2 Answers2

2

  1. No. Your recursive algorithm works in exactly the same time as the number of divisors. Any algorithm which works asymptotically faster cannot print all these numbers.

  2. Yes. Any recursive algorithm may be rewritten in a non-recursive way using the std::stack to store local variables. But, in your case this will not probably be faster and will make the code much less readable, so such rewrite is undesirable. If necessary, I can provide you code.

alexeykuzmin0
  • 6,344
  • 2
  • 28
  • 51
  • Thanks. I'll keep the recursive method then. I'm thinking I only need to recurse if power < x_i / 2, as I can get the other factor by dividing the original number by this factor... maybe... I'll try. Thanks a lot though :) – xylon97 Aug 22 '16 at 11:23
2

Without recursion, it may look like:

bool increase(const std::vector<std::pair<std::size_t, std::size_t>>& v,
              std::vector<std::size_t>& it)
{
    for (std::size_t i = 0, size = it.size(); i != size; ++i) {
        const std::size_t index = size - 1 - i;
        ++it[index];
        if (it[index] > v[index].second) {
            it[index] = 0;
        } else {
            return true;
        }
    }
    return false;
}

std::size_t pow(std::size_t n, std::size_t power)
{
    std::size_t res = 1;
    for (std::size_t i = 0; i != power; ++i) {
        res *= n;
    }
    return res;
}

void do_job(const std::vector<std::pair<std::size_t, std::size_t>>& v,
            std::vector<std::size_t> it)
{
    std::size_t res = 1;
    for (std::size_t i = 0; i != v.size(); ++i) {
        res *= pow(v[i].first, it[i]);         
    }
    std::cout << res << std::endl; 
}

void iterate(const std::vector<std::pair<std::size_t, std::size_t>>& v)
{
    std::vector<std::size_t> it(v.size(), 0);

    do {
        do_job(v, it);
    } while (increase(v, it));
}

Demo

So basically, we count from {0, 0, 0, 0} to {2, 1, 1, 2}.

Jarod42
  • 203,559
  • 14
  • 181
  • 302