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

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

วิธีการแก้ปัญหา

• count = 0
• สร้างอาร์เรย์ prime ขนาด n + 1 และเติมด้วย False
• สำหรับ i = 0 ถึง n:
  • ถ้า prime[i] = false:
    • เพิ่ม count ขึ้น 1
    • ตั้ง j = 2
    • while 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