素数筛选法

什么是素数，大家都比较熟悉。但是如何判定一个数是否为素数呢？经典的判定方法，就是把它的定义依据：除了1和它自身之外，不能被其它的数整除，那么这个数就是素数。

下面是朴素的素数判定法：

bool judgeIsPrime(int number)
{
    if (number <= 1)
        return false;
    else
    {
        for (int i = 2; i <= number - 1; ++i)
            if (number % i == 0)
                return false;
    }
    return true;
}

想一想，我们是否可以对上面的算法进行优化。那么该如何对经典的素数判定法进行优化呢？我们可以这样考虑：对于一个整数n，如果其在整数范围[2,n^1/2]存在因数y，即 n % y == 0;我们假设x = n / y，那么x也是n的一个因数，并且x在[n_^1/2,n-1]范围内。因为x * y = n，所以我们可将枚举比较的范围缩小到[2,n^1/2]。

下面给出优化的素数判定法：

bool judgeIsPrimeOp1(int number)
{
    if (number <= 1)
        return false;
    else
    {
        int end = (int)sqrt(number)  + 1;
        for (int i = 2; i <= end; ++i)
            if (number % i == 0)
                return false;
    }
    return true;
}

通过上面的优化我们将比较的范围大大的缩小，但是它还没有到达最终的优化。

好，我们来进行一种相对前两种更加优化的素数判定法。

我们知道若是一个整数不是素数，也不是0和1的话，那么这个整数就一定是个合数。合数的定义也是相对于素数而言的，不再多讲。

那么假如这个整数是合数，则一定存在一个小于它的素数作为其因数。比如9是一个合数，而素数3就是它的一个因数。

我们可以从这个思路往下走，假如我们知道了小于一个数的所有素数，则只需确定该数能不能被这些素数整除即可。如果不能被整除，则这个数一定是个素数。反之，则不是。从另外一个角度来说，当我们获得一个素数时，可以将它所有的倍数都标记为非素数，这样当我们遍历到一个数时，他没有被任何小于它的素数标记为非素数，则可以确定该数是个素数。

从上面的分析，可以看出我们要初始化一个较大范围内的整数，并将其中的非素数标记出来。假设我们将范围定在[2,10000]。

下面是具体的算法：

int prime[10000];
int primeSize;
bool mark[10001];
void init()
{
    for (int i = 1; i <= 10000; ++i)
        mark[i] = false;
    primeSize = 0;
    for (int i = 2; i <= 10000; ++i)
    {
        if (mark[i] == true)
            continue;
        prime[primeSize++] = i;
        for (int j = i*i; j <= 10000; j += i)
        {
            mark[j] = true;
        }
    }
}

bool judgeIsPrimeOp2(int number)
{
    init();
    if (mark[j] != true)
        return true;
    else
        return false;
}

该算法的时间复杂度为O(1)，相对算法1时间复杂度O(n)，算法2时间复杂度O(n^1/2)来说，其效率是量级的。

从上面的算法中也可以看出，算法的优化是以增加空间辅助为代价的。这也是以空间换时间。