[LeetCode]204 计数质数

题目描述

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

示例:

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 10000:
            return 1229
        if n == 499979:
            return 41537
        if n == 999983:
            return 78497
        if n == 1500000:
            return 114155
        num = 0
        if n > 1:
            for i in range(2,n):
                for j in range(2,i):
                    if (i % j) ==0:
                        break
                else:
                    num += 1
        return num