Project Euler Problem 27小结

Project Euler上有很多有意思的问题，刚做到第27题，对这个问题做个小结。

Problem 27：

Euler有一个著名的方程n^2+n+41，当n=0到39时，方程结果均为质数。如今人们用电脑计算，发现了另一个方程n^2-79n+1601，当n=0到79时，方程结果也均为质数。

设一方程形如n^2+an+b，其中|a|<1000，|b|<1000，n为从0开始的连续自然数。

求使得公式能获得最多质数的a和b，输出结果为a*b。

问题很简单，首先写好判断质数的方法：

bool isPrime(int Num)
{
    for(unsigned long int n=2; n<=sqrt(Num);n++)
    {
        if(Num%n == 0)
        {
            return false;
        }
    }
 
    return true;
}

然后直接穷举遍历，搜索符合条件的a和b，写出程序第一版：

void Euler_Cal_27()
{
    int n=0;
    int maxn = 0;
    int expr = 0;
    int result = 0;
   
    for(int a=-999; a<1000; a++)
    {
        for(int b=-999; b<1000; b++)
        {
            n = 0;
            expr = n*n + a*n + b;
 
            while(isPrime(expr) &&expr>0)
            {
                n++;
                expr = n*n + a*n + b;
            }
 
                if( n>maxn )
                {
                    maxn = n;
                    result = a*b;
                }
            }
        }
    }
 
    cout<< result <<endl;
}

电脑CPU是E6600，得到正确结果用时1.4s。虽然用时不长，但是搜索范围很小，所以肯定有提高的余地。优化自然先从循环着手，仔细检查一下发现while循环条件顺序有误。&&运算只要前一个条件为假就不进行后面条件的判断，而这里恰恰将判断质数放在判断正负这种简单运算前面，影响速度。所以调换条件顺序，此时程序运行时间减少至0.3s。又看了一会儿之后再没想到其他优化方法，所以上论坛看看其他人是如何解决的。一看果然有收获。

1、 n须从0开始，所以当n=0时，方程结果必为质数，否则此时的a和b肯定不是最优结果。而n=0时，方程结果是b，所以b必须为质数。

2、 当n=1时，方程结果为1+a+b，质数必须大于0，所以有a>-b-1。即确定b后，可以缩小a的搜索范围。

还有人事先生成质数表，通过查表来判断质数，减少运行时间。但是这种方法在改变搜索范围时需要重新生成质数表，有些麻烦，所以没有使用。仅依照以上提到的两个条件进行优化，第二版代码如下：

voidEuler_Cal_27()
{
    int n=0;
    int maxn = 0;
    int expr = 0;
    int result = 0;
 
    for(int b=1; b<1000; b++)
    {
        if(isPrime(b))
        {
            for(int a=-b; a<1000; a++)
            {
                n = 0;
                expr = n*n + a*n + b;
 
                while( expr>0 && isPrime(expr) )
                {
                    n++;
                    expr = n*n + a*n + b;
                }
 
                if( n>maxn )
                {
                    maxn = n;
                    result = a*b;
                }
            }
        }
    }
 
    cout<< result <<endl;
}

此时程序运行时间减少至0.17s。

从这次优化小程序发现，优化程序时大多从代码本身入手，忽略问题，不去想原理，在进一步提高程序性能的时候容易遇到瓶颈。以后要注重锻炼自己理解问题的能力，基础还是很差，需要提高。