输入一个正整数，如何找到比它小的最大质数呢？如果你已经忘了什么是质数，这里简单科普一下：除了1和它自身之外，不能被其它数字整除的数，叫做质数。并且，1不是质数。

接下来，我们先把代码的框架写好：

#include <stdexcept>
#include <iostream>

using std::cin;
using std::cout;
using std::cerr;
using std::endl;

using std::invalid_argument;

bool is_prime(unsigned int n) {
    // How can we implement this?
}

unsigned int largest_prime(unsigned int n) {
    unsigned int candidate = n - 1;

    while (candidate > 1) {
        if (is_prime(candidate)) {
            return candidate;
        }

        --candidate;
    }

    throw invalid_argument(“Invalid number");   
}

int main() {
    unsigned int number;

    cout << "Input a number: ";
    cin >> number;
    

    try {
        unsigned int n = largest_prime(number);
        cout << "Largest prime smaller than " << number << " is " << n << endl;
    }
    catch (const invalid_argument& e) {
        cerr << e.what() <<endl;
    }

    return 0;
}

接下来的问题，就变成我们如何实现is_prime了。

无脑实现版

先来看一个最无脑的做法：

bool is_prime(unsigned int n) {
    for (unsigned int i = 2; i < n; ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

从2一直遍历到n-1，只要发现能能整除n的数字，n就不是质数，否则就是质数。虽然这样可以工作，但是十有八九这样的答案不会让你通过面试，因为你错过了太多可以优化的地方了。

试一半就够了

其实，稍微想一下就会发现，一个数如果可以被1和它自己之外的数整除，这个数最小就是2了。这也就意味着，我们只要检查[2, n/2)，如果都没发现可以整除n的数字，后面的也就不用再查了：

bool is_prime(unsigned int n) {
    for (unsigned int i = 2; i < (n/2); ++i) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

这个答案如何呢？估计你还是有80%的概率无法通过面试，因为你都想到一半了，再往前多想一点，你又能省掉一半的运算。

在一半里试验质数

在上面这个实现的for循环里，可以预见，如果n不能被2整数，那么它也注定无法被后续的所有偶数整数。因此，我们只要检查[3, n/2)上所有的奇数就行了，而不用检查所有的数：

bool is_prime(unsigned int n) {
    if (n % 2 == 0) {
        return false;
    }
    
    for (unsigned int i = 3; i < (n/2); i += 2) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

这样，是不是就已经足够优化了呢？应该说，对于这个题，你还是有30%的概率无法通过面试。为什么呢？

其实只查到n的平方根就行了

我们来观察几个数字：

• 25: 1 25 / 5 5
• 100: 1 100 / 2 50 / 4 25 / 5 20 / 10 10

发现什么了么？实际上，一个数字的所有因数，都是成对出现的。在这一对数字中，一个极端情况，就是两个因数相等（例如5x5和10x10）。而其他的情况，则是一个因数大于n的平方根，一个因数小于n的平方根。因此，实际上我们只要从2开始，查找到n的平方根就好了，而不用查找到n/2。于是，is_prime还可以优化成这样：

bool is_prime(unsigned int n) {
    if (n % 2 == 0) {
        return false;
    }

    for (unsigned int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

明显循环的次数又降低了。应该说，如果你给出这样的答案，至多，你只有5%的可能性会在面试的时候失败。并且，面试你的人多多少少有点苛求。那么问题在哪呢？难道还有可以优化的空间么？

再优化一点点？

其实，在这个is_prime的实现里，我们的循环是在从3开始的奇数中进行排除的，但是，如果一开始我们再把“可以被3整除”这个条件排除掉，就可以让循环按照2和3的最小公倍数，也就是6作为step循环，进一步降低循环次数：

bool is_prime(unsigned int n) {
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }

    for (unsigned int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }

    return true;
}

当然，在我们这个例子中，is_prime是作为辅助函数实现的。如果is_prime作为一个更严格的API去实现，我们应该判断n <= 1的情况：

bool is_prime(unsigned int n) {
    if (n <= 3) { return n > 1; }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }

    for (unsigned int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }

    return true;
}

实际上，这份实现，也是现如今应用的最广泛的一个判断质数的方法。如果在面试中可以交出这样的答卷，相信不会再有人因为技术问题拒绝你了，不过我也承认，如若不是你事先早有准备，几乎不可能临场发挥的如此完美 :]

那个。。。还能再快点儿么？

但是，故事到此还没结束。实际上，如果我们限定一些条件，还可以进一步改善质数判断的性能。只不过这种改善相比我们之前的过程，就完全是一种质变了。因为它把这个判断的过程，从运行时搬到了编译时。在下一篇黑板报里，我们还是用求质数举例，来感受下模板元编程的魅力。