ChunNote
0%

leetCode-204:Count Primes

发表于 分类于

问题描述

给定一个数，要求找出比这个数小的质数的个数。题目链接：**点我**

样例输入输出

输入：10

输出：4

解释：质数为：2，3，5，7

输入：1

输出：0

问题解法

此题最简单的解法是遍历每个数，分别对每个数进行判断，但是这样时间复杂度太高。优化一点的做法是，遍历前 sqrt(n) 的数，对于每个质数，分别 *2、*3、*4... 得到新的数，这些数绝对是合数，后续不用再判断，再优化一点的做法是，对每个质数 a，从 a * a 开始计算，因为 a * 2、 a * 3、 a * 4、 a * 5、 a * (a - 1) 都在之前的 2、3、4、5、...、a - 1中计算过。代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution
{
    public int countPrimes(int n)
    {
        boolean[] isPrimes = new boolean[n];
        for (int i = 0; i < n; i++)
        {
            isPrimes[i] = true;
        }

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

        int count = 0;
        for (int i = 2; i < n; i++)
        {
            if (isPrimes[i])
            {
                count++;
            }
        }

        return count;
    }
}