如何快速解决欧拉计划题：素数问题

翻译成中文，第三题的题目是这样的：

13195的质数因子有5,7,13和29.

600851475143的最大质数因子是多少？

当然这个题目的思路是很简单的

第一：找出他所有的因数，

第二：看他的因数是不是质数；

但是这里要求程序在一分钟内得到结果，

我先来看我最初的设计：

[plain]
use strict;
use warnings;
use bignum;
my $num;
my $i;
my $cout=2;

while($cout<300425737571)
{

    if(0==600851475143%$cout)
    {
        print $cout."\n";
    }
    $cout++;
}

这里先找的是她的因数；结果电脑运行了一晚上，还没有得到最后的结果，如下：
[plain]
C:\WINDOWS\system32\cmd.exe /c perl "F:\perl\c.
71
839
1471
6857
59569
104441
486847
1234169
5753023
10086647
87625999

那么这样做到底可行吗？其实我们可以通过一个简单的修改达到大大减小运行时间；
其实我们在得到71这个因数的同时，我们也得到了另一个因数：8 462 696 833。这里我们可以得出最大的因数是8462696833.所以我们循环的时候把这一点加上。

[plain]
use strict;
use warnings;
use bignum;
my $num;
my $i;
my $cout=2;
my $another;

while($cout<300425737571)
{

    if(0==600851475143%$cout)
    {
        $another = 600851475143/$cout;
        if($another<$cout)
        {
            last;
        }
        else
        {
            print "$cout\n";
            print "$another\n";
        }
    }
    $cout++;
}

速度快多了，因为我们从结果中看，只要跑到1234169就会终止运行。越往后，运行的时间就会指数倍的增长。
[plain]
C:\WINDOWS\system32\cmd.exe /c perl "F:\perl\c.pl"
71
8462696833
839
716151937
1471
408464633
6857
87625999
59569
10086647
104441
5753023
486847
1234169
Hit any key to close this window...
然后我们再来筛选质数就可以了。
[plain]
use strict;
use warnings;

my @num;
my $cout=0;
my $num;
my $i;

@num=qw/71 839 1471 6857 87625999 59569 10086647 104441 5753023 486847 1234169 408464633 716151937 8462696833 /;
foreach $num(@num)
{
    for($i=2;$i<$num**0.5;$i++)
    {
        if(0==$num%$i)
        {
            $cout=1;
            last;
        }
    }
    print "$num\n" if($cout==0);
}

结果如下：

[plain]
C:\WINDOWS\system32\cmd.exe /c perl "F:\perl\c.pl"
71
839
1471
6857
Hit any key to close this window...
所以最后的结果是6875.

补充：综合编程 , 其他综合 ,