C++确定K是否可以表示为N的素因数之和

Question

所以我正在写一个可以解决The Centrifuge Problem的程序，我的算法中有一个特殊的部分遇到了问题。我需要取两个整数变量N和K，并确定K是否可以表示为N的素因数之和。

例如，N= 21，K= 6: 21的素数因子是3 x 7.6。6可以表示为3+3，因此这是正确的。另一个例子N= 21，K=11.11不能表示为3或7的任意组合，因此为假。

在我的程序中，到目前为止我解决这个问题的最佳想法是使用以下代码找到N的质因数，然后将这些值存储到一个向量中：

vector<int> PrimeFactors(int n)
{
    vector<int> factors;

    while (n % 2 == 0)
    {
        factors.push_back(2);
        n = n / 2;
    }

    for (int i = 3; i <= sqrt(n); i = i + 2)
        while (n % i == 0)
        {
            factors.push_back(i);
            n = n / i;
        }

    if (n > 2)
        factors.push_back(n);

    return factors;
}

问题是，我不知道如何取向量的项，并确定K的值是否可以表示为这些值的总和。

有人能给我一个正确的方向，或者提出一个更好的方法来解决我的问题的这一部分吗？

Answer 1

您可以使用递归：

bool isSum(const std::vector<int>& F, const int K)
{
  for (const auto& f: F)
  {
    if (f > K)
    {
      break;
    }
    else if (f == K)
    {
      return true;
    }
    else if (f < K)
    {
      if (isSum(F, K - f))
      {
        return true;
      }
    }
  }
  return false;
}

我在这里假设向量F中的所有因子都是按升序排序的。

但是，我怀疑你的因式分解函数不能正常工作。