如何使用 Perl 对整数进行因式分解？

Question

我想将整数拆分为它们的因子。 例如，如果记录总数为：

169 - ( 13 x 13 times) 
146 - ( 73 x 2 times) 
150 - ( 50 x 3 times)
175 - ( 25 x 7 times)
168 - ( 84 x 2 ) 
160 - ( 80 x 2 times) 

当超过 10k 时 - 我希望所有内容都为 1000 当它超过 100k 时 - 我希望一切都在 10k 上

，这样我想对数字进行因式分解。 如何实现这一目标？ 有没有 Perl 模块可用于此类数字运算？

假设记录总数为 10k。 它应该只被分割1000x10次； 不是 100 或 10 秒。

我可以使用 sqrt 函数。 但这并不总是我所期待的。 如果我输入 146，我必须得到 (73, 2)。

Answer 1

循环遍历可接受范围内的一些常见数字（例如 9 到 15），计算测试数字的余数，然后选择最小值。

sub compute_width {
    my ($total_records) = @_;
    my %remainders;
    for(my $width = 9; $width <= 15; $width += 1) {
      my $remainder = $total_records % $width;
      $remainders{$width} = $remainder;
    }
    my @widths = sort { 
      $remainders{$a} <=> $remainders{$b} || 
      $a <=> $b 
    } keys %remainders;
    return $widths[0];
}

Answer 2

如果数字不是质数，则可以使用因式分解算法。

这里有一个这样的函数的例子： http://www.classhelper.org/articles/perl-by-example-factoring-numbers/factoring-numbers-with-perl.shtml

Answer 3

您可以在 Perl 中使用与其他语言相同的算法。 这些想法中没有任何 Perl 特殊的魔力。 这只是实现，对于像这个问题这样的问题，它可能看起来与任何语言的实现非常相似。

您想解决什么问题？ 如果我们知道您想要做什么，也许我们可以为您指出正确的算法：

• 为什么超过 10,000 的数字必须使用 1,000 因子？ 大多数数字都没有 1,000 因数。
• 您想要所有因子，还是只想要最大的因子及其伴生因子？
• sqrt 函数没有按您的预期工作是什么意思？ 如果您遵循通用算法，则只需迭代到平方根的下限即可测试因子。 大多数整数没有整数平方根。