本文共 1911 字，大约阅读时间需要 6 分钟。

题目大意：

统计所有小于非负整数 n 的质数的数量。

示例:

输入: 10输出: 4解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

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

1. 是质数，同时划去所有2的倍数，接着查看剩下的数
2. 是质数，同时划去所有3的倍数，接着查看剩下的数
3. 一直进行到n的平方根（向上取整）。

当你要画圈的素数的平方大于 n 时，那么后面没有划去的数都是素数，就不用继续判了。如下图：

用数组的思想，0表示False，不是素数，1表示是素数，最后只要统计1的个数就可以了，全部加起来就是了。

class Solution(object):    def countPrimes(self, n):        """        :type n: int        :rtype: int        """        if n < 3:       # 注意审题边界条件,是小于n,不包括n            return 0    # 注意 数组越界的情况                primes = [1] * n  # 先全部设为都是素数        primes[0] = primes[1] = 0  # 0和1不是素数        for i in range(2,int(n**0.5)+1):   # 在选择除数时候的一个小技巧.大于一半的数是不可能做除数的            if primes[i] == 1:  # 如果是素数，就把他的倍数都设为非素数，即0                primes[i*i:n:i] = [0]*len(primes[i*i:n:i])  # 用埃氏筛法, 将每一个不是素数的数筛选掉        return sum(primes)

python里list的特性 [::i] 取i的倍数。

s[i:j:k] = t    #the elements of s[i:j:k] are replaced by those of t

s[i : j : k] 代表的意思是列表 s 中的第 i 个元素(包含), 到第 j 个元素(不包含)，每隔 k 个数取一个 形成的列表，即取[j , k)，步长为 k取出的列表子集。

把 s[i : j: k]中的元素替换成 t 中的对应的元素，所以 t 的长度（元素的个数）要和 s[i : j: k]的长度一样。

示例：

s = range(10)print s    #输出为[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]Is[0:10:2] = ['I'] * len(s[0:10:2])  #把偶数都替换为字符print s    #输出为['I', 1, 'I', 3, 'I', 5, 'I', 7, 'I', 9]

以下是Java版本：

素数不能被比它小的整数整除, 建一个boolean 数组, 从2开始, 把其倍数小于N的都删掉。

1.	public class Solution {  2.	    public int countPrimes(int n) {  3.	        if (n <= 2) {  4.	            return 0;  5.	        }  6.	        boolean[] isPrime = new boolean[n];  7.	        for (int i = 2; i * i < n; i++) {  8.	            if (!isPrime[i]) {  9.	                for (int j = i; j * i < n; j++) {  10.	                    isPrime[j * i] = true;  11.	                }  12.	            }  13.	        }  14.	        int count = 0;  15.	        for (int i = 2; i < n; i++) {  16.	            if (!isPrime[i]) {  17.	                count++;  18.	            }  19.	        }  20.	        return count;  21.	    }  22.	}

转载地址：http://apuvi.baihongyu.com/