C++ int 数组指针递归查找质因数

Question

我正在尝试创建一个函数，该函数可以返回数组（或多组，但我正在尝试使用数组）中给定数字的素因数。

例如，如果我输入 12，我想要得到 2、2 和 3，而不是像集合那样得到 2 和 3。这样我就可以使用它们来查看它是否是 Smith 数，所以我需要单独的数字。

另外，我正在采取递归方法。

我尝试了多种方法（但没有成功）返回数组，包括将初始指针传递到代码中，该指针指向存储数组的空间。

我尝试过在函数中初始化数组然后返回它。

据我所知，我可以从基本情况迭代中获取数组，然后当尝试构造一个大小为 oldArray+1 的新数组以将值复制到其中时，事情会变得混乱。这就是我迷路的地方。

根据我所读到的内容，尽管这不是最有效的实现，但我应该能够使其工作。

我有一个函数 nextPrime(int n)，给定 n 将返回该数字的下一个素数。

请参阅下面的源代码：

int* find(int n, int p) {

int root = (int) floor(sqrt(n));
if (p > root) {
    // Base case, array gets initialized and returned
    // depending on value of n and p.
    if (n > 1) {
        factors = new int[1];
        factors[0] = n;
        return factors;
    }
    else {
        factors = new int[0];
        return factors;
    }
}
else
    if (n%p == 0){
        // Inductive step if p is a factor
        int newFloor = (int) floor(n/p);
        factors = find(newFloor, p);

        // Initialize new array.
        int* newFactors;
        newFactors = new int[(sizeof(factors) / sizeof(int)) + 1];

        // Add p to first slot, fill rest with contents of factors.
        factors[0] = p;
        for (int i = 0; i < (sizeof(factors) / sizeof(int)); i++) {
            newFactors[i+1] = factors[i];
        }

        return newFactors;
    }
    else {
        // Inductive step p isn't a factor of n
        factors = find(n, factors, nextPrime(p));
        return factors;
    }
}

正如我所说，错误在于返回数组并使用其值，但为什么它似乎从第一次迭代返回 OK？

Answer 1

像这样的东西可以工作。效率不是很高！！

void FindFactors( int number , std::vector<int>&  factors )
{
    for ( int i = 2; i <= number; ++i )
    {
        if ( number % i == 0 )
        {
            factors.push_back( i );
            FindFactors( number / i , factors);
            break;
        }
    }
}

int main()
{

    std::vector<int> factors;
    FindFactors( 121 , factors );
    return 0;
}

调用函数factors后将仅包含素因数。

Answer 2

为此，您应该使用 std::vector 。您遇到的主要问题是指向数组的指针无法知道数组包含的项目数。具体来说，您说 sizeof(factors) 的部分是错误的。据我了解，您期​​望为您提供由 factors 指向的数组中的项目数，但它实际上为您提供了存储指向 int 的指针所需的字节数。

您应该返回一个 vector 或将其作为参考传递，并在每次找到因子时更新它。