[Algorithm] 高效求素数

最近在写leetcode上的题目的时候发现自己写的筛法求素数的个数的程序并不够快。
我之前写的代码是这样的：

memset(is_prime, true, sizeof(is_prime));
is_prime[0] = is_prime[1] = false;
for (int i = 2; i < N; ++i) {
    if (is_prime[i]) {
        for (int j = 2; j * i < N; ++j)
            is_prime[j] = false;
        ++cnt;
    }
}

其实这里有一些地方可以优化的，首先第二个循环里，j并不需要从2开始，以为在j小于i的情况下其实j*i里面肯定含有比i小的素数，因此，都已经被筛掉了。因此第二个循环可以改成这个样子：

for (int j = i; j * i < N; ++j)

其次，第一个循环里，由于大于$\sqrt{N}$的素数的倍数肯定小于$\sqrt{N}$。因此第一个循环只需要到$\sqrt{N}$就可以了。

最后就是这个样子：

is_prime[0] = is_prime[1] = false;
for (int i = 2; i * i < n; ++i) {
    if (is_prime[i]) {
        for (int j = i * i; j < n; j += i)
            is_prime[j] = false;
    }
}