LeetCode 204. Count Primes

题目

Count the number of prime numbers less than a non-negative number, n.

分析

计算小于给定数的素数有多少个,这里用到了非常经典的从小到大排除的方法

  • 输入:一个正整数 num
  • 条件:小于这个 num
  • 任务:求小于这个 num 的素数的个数
  • 输出:个数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n < 3:
return 0
primes = [True] * n
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
return sum(primes)

点评

首先一定要注意,求的是小于 n 的,不包括 n,这里用到了非常经典的从小到大排除的方法,如果一个数 num 是素数,那么从它的平方开始,后面的每一个步长为 num 的数都不是素数