204. 计数质数

题目描述

输入整数 n，统计严格小于 n 的质数有多少个，返回这个个数。

质数是大于 1、且只能被 1 和自身整除的整数。

示例 1

输入：n = 10
输出：4

解释：小于 10 的质数是 2、3、5、7，共 4 个。

示例 2

输入：n = 0
输出：0

解释：没有小于 0 的质数。

示例 3

输入：n = 1
输出：0

解释：没有小于 1 的质数。

数据范围

0 <= n <= 5 * 10^6

解题思路：埃拉托斯特尼筛

埃拉托斯特尼筛。先假设 2..n-1 都是质数，从小到大枚举 i；如果 i 还被标为质数，就把它的倍数 i·i, i·i+i, … 全部划掉。只需枚举到 i·i < n，因为任何合数都有一个不超过其平方根的质因子。最后数一下还剩多少个质数。

为什么正确

处理完 i 后，所有含有不超过 i 的质因子的合数都已被划掉。

复杂度分析

时间 O(n log log n)，空间 O(n)。

易错点

题目要的是“小于 n”，不包含 n 本身。内层从 i·i 开始划即可，更小的倍数已经被更小的质因子划过；在 C++/Java 里 i·i 可能溢出，要用 long。逐个试除判断质数在 n = 5×10^6 时会超时。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0
        is_prime = [True] * n
        is_prime[0] = is_prime[1] = False
        i = 2
        while i * i < n:
            if is_prime[i]:
                for j in range(i * i, n, i):
                    is_prime[j] = False
            i += 1
        return sum(is_prime)

class Solution {
    public int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (long i = 2; i * i < n; i++) {
            if (isPrime[(int) i]) {
                for (long j = i * i; j < n; j += i) {
                    isPrime[(int) j] = false;
                }
            }
        }
        int cnt = 0;
        for (boolean b : isPrime) if (b) cnt++;
        return cnt;
    }
}

class Solution {
public:
    int countPrimes(int n) {
        if (n < 3) {
            return 0;
        }
        vector<bool> isPrime(n, true);
        isPrime[0] = isPrime[1] = false;
        for (long long i = 2; i * i < n; i++) {
            if (isPrime[i]) {
                for (long long j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        int cnt = 0;
        for (int k = 0; k < n; k++) cnt += isPrime[k];
        return cnt;
    }
};

func countPrimes(n int) int {
	if n < 3 {
		return 0
	}
	isPrime := make([]bool, n)
	for k := range isPrime {
		isPrime[k] = true
	}
	isPrime[0], isPrime[1] = false, false
	for i := 2; i*i < n; i++ {
		if isPrime[i] {
			for j := i * i; j < n; j += i {
				isPrime[j] = false
			}
		}
	}
	cnt := 0
	for _, b := range isPrime {
		if b {
			cnt++
		}
	}
	return cnt
}

var countPrimes = function(n) {
    if (n < 3) {
        return 0;
    }
    const isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime.filter(Boolean).length;
};

function countPrimes(n: number): number {
    if (n < 3) {
        return 0;
    }
    const isPrime: boolean[] = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false;
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime.filter(Boolean).length;
}

载入编辑器，自己跑一遍 →

其他解法

埃氏筛中一个合数会被它的每个质因子重复标记；线性筛只让最小质因子去标记，去掉了重复工作，从 O(n log log n) 降到 O(n)。

解法 2：线性筛（欧拉筛）时间 O(n)，空间 O(n)

从小到大枚举 i，如果 i 没有被标记就把它加入质数表。然后用质数表中的每个质数 p 去标记 i*p 为合数；一旦 i 能被 p 整除就停止，因为更大的质数 q 乘以 i 得到的合数，其最小质因子是 p 而不是 q，应该留给后面的 i 去标记。这样每个合数只会被它的最小质因子标记一次。

每个合数只标记一次，理论复杂度严格 O(n)，并且顺便得到了质数表。需要额外保存质数列表，“i 能被 p 整除就停止”这一步需要理解才能写对。

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 3:
            return 0
        # 偶数中只有 2 是质数，只对奇数做线性筛，奇数 i 只需乘奇质数 p
        is_composite = bytearray(n)
        primes = []
        for i in range(3, n, 2):
            if not is_composite[i]:
                primes.append(i)
            for p in primes:
                if i * p >= n:
                    break
                is_composite[i * p] = 1
                if i % p == 0:
                    break
        return len(primes) + 1

class Solution {
    public int countPrimes(int n) {
        boolean[] isComposite = new boolean[Math.max(n, 0)];
        int[] primes = new int[Math.max(n, 0)];
        int cnt = 0;
        for (int i = 2; i < n; i++) {
            if (!isComposite[i]) primes[cnt++] = i;
            for (int k = 0; k < cnt; k++) {
                int p = primes[k];
                if ((long) i * p >= n) break;
                isComposite[i * p] = true;
                if (i % p == 0) break;
            }
        }
        return cnt;
    }
}

class Solution {
public:
    int countPrimes(int n) {
        vector<bool> isComposite(max(n, 0));
        vector<int> primes;
        for (int i = 2; i < n; i++) {
            if (!isComposite[i]) primes.push_back(i);
            for (int p : primes) {
                if ((long long)i * p >= n) break;
                isComposite[i * p] = true;
                if (i % p == 0) break;
            }
        }
        return primes.size();
    }
};

func countPrimes(n int) int {
	if n < 2 {
		return 0
	}
	isComposite := make([]bool, n)
	primes := []int{}
	for i := 2; i < n; i++ {
		if !isComposite[i] {
			primes = append(primes, i)
		}
		for _, p := range primes {
			if i*p >= n {
				break
			}
			isComposite[i*p] = true
			if i%p == 0 {
				break
			}
		}
	}
	return len(primes)
}

var countPrimes = function(n) {
    const isComposite = new Uint8Array(Math.max(n, 0));
    const primes = [];
    for (let i = 2; i < n; i++) {
        if (!isComposite[i]) primes.push(i);
        for (const p of primes) {
            if (i * p >= n) break;
            isComposite[i * p] = 1;
            if (i % p === 0) break;
        }
    }
    return primes.length;
};

function countPrimes(n: number): number {
    const isComposite = new Uint8Array(Math.max(n, 0));
    const primes: number[] = [];
    for (let i = 2; i < n; i++) {
        if (!isComposite[i]) primes.push(i);
        for (const p of primes) {
            if (i * p >= n) break;
            isComposite[i * p] = 1;
            if (i % p === 0) break;
        }
    }
    return primes.length;
};

数学专题的其他题目

查看数学全部题目 →