我正在尝试解决一些在线难题，找出一个非常大的数的最大质因数(7393913335919140050521110339491123405991919445111971 是准确的)。在寻找解决方案时，我偶然发现了这段 Perl 代码 ( from here ):

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 ) ) );
}

With as auxiliaries(好像没问题):

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 也不太适合对原始代码进行逆向工程。有人知道我遗漏了什么吗？

==UPDATE:问题已(在某种程度上)通过变通办法解决

最佳答案

回答翻译问题...

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

为了证明这一点 - 在 1148487369611039 上尝试 - 它有素因子 104717、104723 和 104729。没有更正 - 它输出 104723，有了更正，你会得到正确的答案:104729

算法点评

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

您可以使用各种技巧来加快速度，具体取决于您希望获得答案的确定性。一种是预先测试任何候选人的素数 - 例如使用 BigInteger.isProbablePrime() 插入测试作为 goAtIt() 中的测试，如果您在过程的早期获得非常大的素数，则提前返回。如果你不喜欢它的概率元素，你可以自己推出 Miller-Rabin primality deterministic test .您还可以构建素数表，并且只在任何试验划分和/或查找中使用它们。您也可以考虑 Pollard-Strassen algorithm

¹_{(我在 goAtIt() 中的 while 循环之后放置了一个输出，以检查它何时真正找到了解决方案)}

Perl 大数注意事项

Small problem with Perl is that it doesn't accept really big numbers

我认为它比那更糟糕，因为 Perl 会隐式地 turn the large integer into a double precision floating point如果你只是更换

my $magic = <number>;

与

my $magic = 7393913335919140050521110339491123405991919445111971;

所以 - 它会给出错误的答案，而不是像 ideone here 上展示的那样抛出错误.相当讨厌，因为该算法适用于小数字，如果与较大的输入一起使用，可能会使粗心的用户产生错误的安全感......

关于java - 从 Perl 到 Java，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28162144/