迭代等价于递归算法

Question

我正在尝试将这个程序修改为等效的迭代，但这对我来说变得非常困难，因为到目前为止我还是一个新手，它涉及到一种将数字分解为其素因数的算法，这里是代码：

#include <iostream>
#include <map>
#include <cmath>
std::map< int, std::pair<int, int> > decompositions;
void descompon_number(int num, int root, int i = 2 )
{
    auto iterator = decompositions.find(num);
    if (iterator == decompositions.end())
    {
        if (num > 1 && i <= root)
        {
            if (num % i == 0)
            {
                int n = num / i;
                decompositions[num] = std::make_pair(i, n);
                descompon_number(n, (int) std::sqrt(n));
            }
            else
                descompon_number(num, root, i + 1);
        }
        else
            decompositions[num] = std::make_pair(num, 1);
    }
}
void show(int num, int factor, int exponent, int see)
{
    auto pair = decompositions[num];
    if (num <= 1 || factor != pair.first)
    {
        if (see)
            std::cout << factor;
        if (exponent > 1 && see)
            std::cout << "^" << exponent;
        if (pair.first > 1 && see)
            std::cout << " * ";
        exponent = 0;
    }
    if (num > 1)
        show(pair.second, pair.first, exponent + 1, see);
}
void descompon(int a, int b, int see)
{
    if (a <= b)
    {
        descompon_number(a, (int) std::sqrt(a));
        if (see)
            std::cout << a << " = ";
        show(a, decompositions[a].first, 0, see);
        if (see)
            std::cout << std::endl;
        descompon(a + 1, b, see);
    }
}
int main()
{
    descompon(2, 100, 1);
    return 0;
}

有人可以帮助我解决这个问题

Answer 1

迭代查找素因数并不是很复杂。

这是如何执行此操作的伪代码。

让我们P是前n个素数的列表，这样Pn <= sqrt(m) .

array findPrimeFactors(m)
    answer = new array
    for p in P
        while m can be divided by p
            m = m / p
            answer.append(p)
        if m == 1
            break
    return answer 

注意：如果 m 是素数，则返回空数组。

Answer 2

您可以使用 erastotenes 筛子来计算素数，稍后您可以使用 popovitsj 发布的算法。

以下代码可以优化，但其主要目的是向您展示如何继续。

完整示例：

#include <iostream>
#include <vector>
using namespace std;
// Returns a vector containing the first <number> prime numbers
vector<int> erastotenes_sieve(int number)
{
    vector<int> result;
    int *sieve = new int[number]; 
    for (int i = 0; i < number; i++) sieve[i] = 0;

    // Traverse the sieve marking multiples.
    for (int i = 2; i < number / 2; i++)
        for (int j = i + i; j < number; j += i)
            sieve[j] = 1;
    // Collect unaffected indexes, those are prime numbers.
    for (int i = 2; i < number; i++)
        if (!sieve[i])
            result.push_back(i);
    delete [] sieve;
    return result;
}
vector<int> descompon_number(int number)
{
    vector<int> result;
    if (number == 1 || number == 0)
    {
        result.push_back(number);
        return result;
    }
    for (int &prime : erastotenes_sieve(number))
    {
        while (number % prime == 0 && number != 1)
        {
            number /= prime;
            result.push_back(prime);
        }
    }
    return result;
}

int main()
{
    for (auto &i : descompon_number(20))
    {
        cout << i << endl;
    }
    return 0;
}