при условии, что простая факторизация числа повторяется через все факторы в C++ без рекурсии

Question

Мне дана простая факторизация числа p1^x1 * p2^x2 * .... на карте. Мне нужно перебирать все его факторы, как простые, так и составные. Мне удалось написать решение, используя рекурсию.

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

Вопросы:

1) Есть ли более быстрый способ создания этих факторов?

2) Если возможно, могу ли я заменить рекурсию на цикл while?

Answer 1

1. Нет. Рекурсивный алгоритм работает ровно в то же время, что и число делителей. Любой алгоритм, который работает асимптотически быстрее, не может печатать все эти числа.

2. Да. Любой рекурсивный алгоритм может быть переписан нерекурсивным способом с использованием std::stack для хранения локальных переменных. Но в вашем случае это, вероятно, не будет быстрее и сделает код менее понятным, поэтому такой переписывать нежелательно. При необходимости я могу предоставить вам код.

Answer 2

Без рекурсии, это может выглядеть следующим образом:

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

Поэтому в основном мы рассчитывать от {0, 0, 0, 0} до {2, 1, 1, 2}.