用 Python 統計質數

假設我們有一個上限 n。我們必須統計在範圍 2 到 n 中出現的質數數量。因此，如果 n = 10，結果將為 4。因為在 10 之前有四個質數，它們是 2、3、5、7。

為解決此問題，我們將遵循以下方法 −

• count = 0
• 建立一個大小為 n + 1 的陣列 prime =，並用 False 填充它
• 對於 i = 0 到 n，執行
  • 如果 prime[i] = 假，則
    • count 增加 1
    • 設定 j = 2
    • 當 j * i <n 時，則
      • prime[i * j] = True
      • j = j + 1
• 返回 count

示例

讓我們看看以下實現以更好地理解 −

 線上演示

class Solution(object):
   def countPrimes(self, n):
      """
      :type n: int
      :rtype: int
      """
      count = 0
      primes = [False for i in range(n+1)]
      for i in range(2,n):
         if primes[i] == False:
            count+=1
            j = 2
            while j*i<n:
               primes[j*i] = True
               j+=1
      return count
ob1 = Solution()
print(ob1.countPrimes(50))
print(ob1.countPrimes(10))

輸入

n = 50
n = 10

輸出

15
4

Arnab Chakraborty

更新於： 28-4 月-2020

4K+ 次觀看

開啟你的職業

完成該課程以獲得認證

開始學習