สร้างรายการจำนวนเฉพาะน้อยกว่า n ใน Python

สมมติว่าเรามีตัวเลข n เราต้องสร้างรายการของจำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ n ในลำดับเพิ่มขึ้น ต้องจำไว้ว่า 1 ไม่ใช่จำนวนเฉพาะ

ตัวอย่าง

หากอินพุตคือ 12 ผลลัพธ์จะเป็น [2, 3, 5, 7, 11]

ขั้นตอนการแก้ปัญหา (Sieve of Eratosthenes)

1. sieve := รายการขนาด n+1 เติมด้วย True
2. primes := รายการใหม่ เริ่มต้นว่าง
3. ลูป i จาก 2 ถึง n:
   • ถ้า sieve[i] เป็น True:
     • เพิ่ม i เข้า primes
     • ลูป j จาก i ถึง n เพิ่มทีละ i:
       • sieve[j] := False
4. คืนค่า primes

การใช้งาน

class Solution:
    def solve(self, n):
        sieve = [True] * (n + 1)
        primes = []
        for i in range(2, n + 1):
            if sieve[i]:
                primes.append(i)
                for j in range(i, n + 1, i):
                    sieve[j] = False
        return primes

ob = Solution()
print(ob.solve(12))

อินพุต

12

เอาต์พุต

[2, 3, 5, 7, 11]