典型算法思想与应用1|暴力枚举法与素数问题

枚举法（Enumeration method）又叫穷举法，试图一一列举所有解空间，所以也叫暴力破解，是一种归纳方法。计算机每秒执行的指令数以MIPS（即每秒百万条指令）为计量单位，可见其速度之快，这就是枚举法能被合理利用的原因所在。利用计算机速度快的特点，圆周率、最大素数的位数得已大幅度提高。

枚举算法思想的最大特点是，在面对任何问题时它会去尝试每一种解决方法。在进行归纳推理时，如果逐个考察了某类事件的所有可能情况，因而得出一般结论，那么这个结论是可靠的，这种归纳方法称作枚举法。

枚举算法的思想是将问题的所有可能的答案一一列举，然后根据条件判断此答案是否合适，保留合适的，丢弃不合适的。在C语言中，枚举算法一般使用while循环实现。使用枚举算法解题的基本思路如下。

① 确定枚举对象、枚举范围和判定条件。

② 逐一列举可能的解，验证每个解是否是问题的解。

枚举算法一般按照如下3 个步骤进行。

① 题解的可能范围，不能遗漏任何一个真正解，也要避免有重复。

② 判断是否是真正解的方法。

③ 使可能解的范围降至最小，以便提高解决问题的效率。

典型应用：求小于n的最大素数问题。

素数是指除了1和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被2~16的任一整数整除。

可以考虑分而治之：

1 先是求某一个数是否是素数

用枚举法，简单枚举就是将全部可能一一枚举，但枚举也是可以优化的。

I 解空间确定，建立简洁的数学模型

模型中变量数尽可能少，它们之间相互独立。

II 减少搜索空间

如某一个数是否是素数的问题，只有奇数才可能是素数，偶数不是素数。

设a * b = n，i * i = n，若a<=i，则必有b>=i 。如8*8=64，则a如果是2、4、8，则b就是32、16、8，反过来也是如此，因此只需判定在2~√64之间有无因子即可。

III 合适的搜索顺序

搜索空间的遍历顺序要与模型中条件表达式一致。

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

2 找某一区间的最大素数

同样需要考虑解空间、搜索空间与顺序，不同的搜索策略有不同的时间效率。

int maxPrime2(int n)
{
    for(int i=n;i>2;i--)
    {
        if(isPrime(i))
            break;
    }
    return i;
}

以下是不同策略的简单测试代码：

#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

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

bool isPrime(int n,int start)
{
    if(n==2)
        return true;
    if(n%2==0)
        return false;
    for(int i=start;i<=sqrt(n);i+=2)
    {
        if(n%i==0)
            return false;
    }
    return true;
}

int maxPrime1(int n)
{
    int max=2;
    for(int i=2;i<=n;i++)
    {
        if(isPrime(i) && max<i)
            max=i;
    }
    return max;
}

int maxPrime2(int n)
{
    for(int i=n;i>2;i--)
    {
        if(isPrime(i))
            break;
    }
    return i;
}

int maxPrime3(int n)
{
    int max=2;
    for(int i=2;i<=n;i++)
    {
        if(isPrime(i,max) && max<i)
            max=i;
    }
    return max;
}

typedef int (*PF)(int);
void test(PF pf,int n)
{
    clock_t start = clock();
    cout<<pf(n)<<endl;
    cout<<"time consumed: "<<clock()-start<<endl;
}

int main()
{
	int n=1234567;
	test(maxPrime1,n);
	test(maxPrime2,n);
	test(maxPrime3,n);
    cin.get();
	return 0;
}
/*
1234547
time consumed: 3198
1234547
time consumed: 0
1234567
time consumed: 93
*/

-End-