3

仅在标题中很难解释，但基本上我创建了一个系统，该系统输入一些数字 N 并输出两个数字（不包括 1 和 N），可以将它们相乘以尽可能接近 N（超过而不是低于）。

这里有几个例子：

  • 25 → 5 & 5。
  • 40 → 5 和 8。
  • 53 → 6 和 9。
  • 13 → 2 和 7。

我有一个方法Factor可以返回 X 无 1 和 X 的所有因子的列表。这段代码也不需要处理大数，所以我通过检查它是否在素数列表中来测试素数。

执行此操作的代码在这里： 

if (primes.Contains(N))
        N++;
List<int> facts = Factor(N);
double root = Math.Sqrt(N);
int cl1;
int cl2;
if (root == (int)root)
{
    cl1 = (int)root;
    cl2 = (int)root;
}
else if (N == 2)
{
    cl1 = 1;
    cl2 = 2;
}
else
{
    cl1 = facts.Aggregate((x, y) => Math.Abs(x - root) < Math.Abs(y - root) ? x : y);
    facts.Remove(cl1);
    cl2 = facts.Aggregate((x, y) => Math.Abs(x - root) < Math.Abs(y - root) ? x : y);
}

什么是概括这一点的好方法，以便它可以给出三个输出，或者四个或五个或九个？（显然我会换出一个数组，但我的意思是代码方面cl1）cl2

4

1 回答 1

1

获取 N 的所有因子是一项非常昂贵的操作。这样做实际上会更快（伪代码）：

For p = floor(sqrt(N)); p>1; --p:    
  q = ceil(N/p);
  error = p*q-N; //always positive
  record=make_tuple(p,q,error);
  //... remember the records with the smallest error

维护记录列表的最佳方式取决于您想要多少。拨打那个号码M。

如果只是几个，那么你可以把它们放在一个列表中，当列表大小达到 2M 时，按错误排序并截断为大小 M。

如果很多，则首先将它们放入具有最大错误的优先级队列中，并且每当大小> M时，删除具有最高错误的那个。最后，您可以以相反的顺序将它们拉出并向后填充输出数组

于 2015-10-25T15:16:27.437 回答