得到X个整数,这些整数相乘可以得到接近Y的数

本文关键字:整数 接近 的数 得到 | 更新日期: 2023-09-27 18:09:45

这很难在标题中解释,但基本上我已经创建了一个系统,输入一些数字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);
}

什么是一个好的方法来概括它,使它可以给出三个输出,或者四个,五个或九个?(显然我会用数组交换cl1cl2,但我的意思是代码明智)

得到X个整数,这些整数相乘可以得到接近Y的数

获取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时,删除错误最大的队列。最后,您可以将它们以相反的顺序拉出来并向后填充输出数组