สร้างรายการของ Primes ที่น้อยกว่า n ใน Python

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

ดังนั้น หากอินพุตเท่ากับ 12 เอาต์พุตจะเป็น [2, 3, 5, 7, 11]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ตะแกรง :=รายการขนาด n+1 และเติม True
• primes :=รายการใหม่ เริ่มต้นว่างเปล่า
• สำหรับฉันในช่วง 2 ถึง n ทำ
  • ถ้า sieve[i] เป็น True แล้ว
    • แทรก i ที่ส่วนท้ายของจำนวนเฉพาะ
    • สำหรับ j ในช่วง i ถึง n ให้อัปเดตในแต่ละขั้นตอนโดย i ทำ
      • ตะแกรง[j] :=เท็จ
• รีเทิร์นไพรม์

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

ตัวอย่าง

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]