牛牛与素数(2)题解

牛牛想知道[7,n)内有多少素数，只不过他不知道怎么做，所以他想请你帮忙。
给定一个数字n，返回[7,n)内有多少素数。

题解：模拟即可，只不过如果使用以下方式不断去计算判断素数还是有点慢的，复杂度O(n^2)，时间上不可接受。

    string solve(int n) {
        // write code here
        int num = n * 7;
        for (int i = 2; i <= int(sqrt(num)); i++)
        {
            if (n % i == 0)
            {
                return "NO";
            }
        }
        return "YES";
    }

我们可以用一个更快的方法，埃氏筛法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。用另外一个数组去存储我们找到的素数，最后我们查询一下那个数组即可。
当然对于本题，最快的方法还是打表啦。。打表可以到O(n)
时间复杂度：
空间复杂度：
参考代码：

class Solution {
public:
    bool is_prime_small[1000009];
    bool is_prime[1000009];
    void segment_sieve(int a, int b)
    {
        for (int i = 0; i * i <= b; i++)
            is_prime_small[i] = true;
        for (int i = 0; i < b - a; i++)
            is_prime[i] = true;
        for (int i = 2; i * i <= b; i++)
            if (is_prime_small[i])
            {
                for (int j = 2 * i; j * j <= b; j += i)
                    is_prime_small[j] = false;
                for (int j = max(2, (a + i - 1) / i) * i; j < b; j += i)
                    is_prime[j - a] = false;
            }
    }
    /**
     * 给定一个数字n，返回[7,n)内有多少素数。
     * @param n int整型 代表题目中的n
     * @return int整型
     */
    int solve(int n)
    {
        // write code here
        int c;
        segment_sieve(7, n);
        int ans = 0;
        c = n - 7;
        for (int i = 0; i < c; i++)
        {
            if (is_prime[i])
                ans++;
        }
        return ans;
    }
};