LeetCode 204. 计数质数

204. 计数质数

题目：给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
链接 https://leetcode.cn/problems/count-primes/

个人思路

1. 先写一个是否为质数的方法：以x（x>=2）为例，从如果x能整除2到x/2的其中一个数，则x不是质数，否则为质数

def iszhishu(n):
    for i in range(2,n//2+1):
        if n % i == 0:
            return False
    return True
1
2
3
4
5

然后进行迭代，判断2到n之间有多少个质数，

class Solution:
    def countPrimes(self, n: int) -> int:
        if n <= 2:
            return 0
        def iszhishu(n):
            for i in range(2,n//2+1):
                if n % i == 0:
                    return False
            
1
2
3
4
5
6
7
8