นับจำนวนเฉพาะใน Python

สมมุติว่าเรามีขีดจำกัด n เราต้องนับจำนวนเฉพาะในช่วง 2 ถึง n ดังนั้นถ้า n =10 ผลลัพธ์จะเป็น 4 เนื่องจากมีสี่จำนวนเฉพาะก่อน 10 จึงเป็น 2, 3, 5, 7

เพื่อแก้ปัญหานี้ เราจะปฏิบัติตามแนวทางนี้ -

• นับ =0
• ใช้อาร์เรย์ไพรม์หนึ่งตัว =ขนาด n + 1 แล้วเติมด้วยเท็จ
• สำหรับ i =0 ถึง n ทำ
  • ถ้าไพรม์[i] =false แล้ว
    • เพิ่มจำนวนขึ้น 1
    • เซต j =2
    • ในขณะที่ j * i
    • prime[i * j] =จริง
    • j =j + 1

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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