leetcode204-- Count Primes.

leetcode204-- Count Primes.

题目

求出小于一个给定的数的质数的个数,用的就是那个经典的找法,即一直去掉前面的数作为因子的数。

class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        
        flag = [True] * n   
        ## 注意这里的第i个就是指的是i这个数,因为找的是小于n的个数,所以最大是n-1,又因为是index是从0开始的,所以就申请长度为n的一个flag,用来标记这个数是不是素数,
        for i in range(2, n):
            if flag[i]:  # 如果当前的这个数是素数,
                res += 1   # 总的结果就加1,
               
                j = 2
                while i*j <n: # 并且还要删掉之后含有这个数作为因子的数。
                    flag[i*j] = False
                    j += 1
                       
        return res

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦