从Perl到Java

Question

我正在尝试解决一些在线难题,找到一个非常大的数字的最大素数因子(准确地说是7393913335919140050521110339491123405991919445111971).在我寻找解决方案时,我偶然发现了这个Perl代码(从这里开始):

use strict;
use warnings;

my $magic = <number>;

sub largestprimef($);
sub max($$);

print largestprimef($magic);

sub largestprimef($) {
    my $n = shift;

    my $i;
    return largestprimef(max(2, $n/2)) if($n % 2 == 0); 
    my $sn = int( sqrt($n) );

    for ( $i = 3 ; $i <= $sn ; $i += 2 ) {
        if ( $n % $i == 0 ) { last; }
    }
    if ( $i > $sn )    #loop ran over, means the number is prime
    {
        return $n;
    }
    else {
        return max( $i, largestprimef( $n / $i ) );
    }
}

sub max($$) {
    return ( sort { $a <=> $b } (@_) )[1];
}

现在该算法似乎有效!Perl的一个小问题是它不接受真正的大数字.所以我改写了

my $magic = <number>;

至

my $magic = Math::BigInt->new(' <number> ');

但这只是运行了很多年龄.所以我把它重写为Java(我更熟悉),这导致了这个:

static final BigInteger two = new BigInteger( "2" );

public static void main( String[] args ) {
    BigInteger number = new BigInteger( "<number>" );

    System.out.println( goAtIt( number ) );
}

static BigInteger goAtIt( BigInteger prime ) {
    if ( isEven( prime ) )
        return goAtIt( prime.divide( two ).max( two ) );

    BigInteger sqrt = sqrt( prime );
    BigInteger comp = new BigInteger( "3" );

    while (sqrt.compareTo( comp ) > 0) {
        if ( prime.remainder( comp ).equals( BigInteger.ZERO ) )
            break;
        comp = comp.add( two );
    }

    if ( comp.compareTo( sqrt ) > 0 )
        return prime;

    return comp.max( goAtIt( prime.divide( comp ) ) );
}

作为辅助设备(看起来很好):

static boolean isEven( BigInteger number ) {
    return number.getLowestSetBit() != 0;
}

static BigInteger sqrt( BigInteger n ) {
    BigInteger a = BigInteger.ONE;
    BigInteger b = new BigInteger( n.shiftRight( 5 ).add( new BigInteger( "8" ) ).toString() );
    while (b.compareTo( a ) >= 0) {
        BigInteger mid = new BigInteger( a.add( b ).shiftRight( 1 ).toString() );
        if ( mid.multiply( mid ).compareTo( n ) > 0 )
            b = mid.subtract( BigInteger.ONE );
        else
            a = mid.add( BigInteger.ONE );
    }
    return a.subtract( BigInteger.ONE );
}

但是我的结果总是关闭......而且我的Perl对原始代码进行逆向工程并不是那么好.有没有人知道我错过了什么？

==更新:问题(某种程度上)通过解决方法解决

Answer 1

回答翻译问题...

你的Java 翻译非常接近。它只有一个问题 - 你的while循环条件应该是>= 0, 而不是>0。有了这个修改，它就会起作用。事实上 - 在某些情况下它将输出第二大素因数。

为了展示这一点 - 试穿一下1148487369611039- 其中有质因数104717, 104723& 104729。没有修正 - 它输出104723，经过修正，你会得到正确的答案：104729

算法评论

正如其他人在评论中指出的那样 - 这并不是做你想做的事情的特别快的方法。事实上，这是一个轻描淡写的说法——速度非常慢。在我的盒子上，花了超过 3 分钟找到正确答案 ( 459905301806642105202622615174502491) ¹，但需要很长时间（也许 500 年，或类似的顺序），通过简单地试除每个奇数来证明该数字是素数直到其平方根（这就是算法的作用）。

您可以使用各种技巧来加快速度，具体取决于您想要获得答案的确定性。一种方法是预先测试任何候选者的素数 - 例如，插入一个具有BigInteger.isProbablePrime()高确定性的测试作为测试goAtIt()，如果您在过程的早期得到一个非常大的素数，则尽早返回。如果您不喜欢其中的概率元素，您可以进行自己的Miller-Rabin 素性确定性测试。您还可以构建素数表，并且仅在任何试除法和/或查找中使用它们。您也可以考虑Pollard-Strassen 算法

^{1 （我在}_{循环之后放置一个输出以检查它何时真正找到了解决方案）whilegoAtIt()}

关于 Perl 大数的注释

Perl 的一个小问题是它不接受非常大的数字

我认为它比那更糟糕，因为如果你简单地替换，Perl 会隐式地将大整数转换为双精度浮点

my $magic = <number>;

和

my $magic = 7393913335919140050521110339491123405991919445111971;

因此，它会给出错误的答案，而不是像ideone中演示的那样抛出错误。相当令人讨厌，因为该算法对于小数字工作得很好，如果与较大的输入一起使用，可能会让粗心的用户产生错误的安全感......