筛选法求质数

作者: 拜仁的月饼 | 来源:发表于2020-08-21 16:33 被阅读0次

    前情提要

    求质数最简单的方法是暴力破解

    def isPrime(n):
        if n < 2: # 如果n比2小的话,你判断它干嘛
          return False
        elif n == 2: # 2是个质数
          return True
    
        res = True
        
        for i in range(3 , n):
            for j in range(2, n):
              if i % j == 0:
                  res = False
                  break
    
        return res
    

    但这样做的效率会很低。有没有办法提高效率呢?

    筛选法的核心就一句话:质数的整数倍不是质数。例如,2是质数,但4、6、8等都不是质数,因为它们分别是2的2倍、3倍、4倍等等。同理,3是质数,6、9、12、15等也都不是质数了。

    那么如何实现呢?

    题目:Leetcode-204.计数质数

    class Solution:
        def countPrimes(self, n: int) -> int:
            if n <= 2:  # 原题目要求是小于n范围内有多少质数?如果小于2的话,那么就没有。
                return 0
            
            isPrime = [True for i in range(n)] # 打表。打一个长度为n的表,表示从0到n-1(包括n-1在内)有哪些是质数。一上来默认全是质数
            isPrime[0] = isPrime[1] = False # 由于0和1什么都不算,所以上来就给它们置为False
    
            for i in range(2, n): # 从2开始计算
                if isPrime[i] is True: # 由于2肯定是质数,所以放心的算吧。这个条件的意思是如果i是质数的话
                    for j in range(2, (n - 1) // i + 1):  # j在2倍到小于n的情况下i的最大倍数的范围
                        isPrime[i * j] = False # i的倍数全置于False
            
            res = 0 # 返回的结果
            for tf in isPrime: # 那么对照筛选出来的正负表
                if tf is True: # 每遇到一个True
                    res += 1 # 返回的结果数加1
            
            return res
    

    相关文章

      网友评论

        本文标题:筛选法求质数

        本文链接:https://www.haomeiwen.com/subject/ekoujktx.html