โปรแกรม Python สำหรับการคัดกรองเอราโธสเธนีส (Sieve of Eratosthenes)

ในบทความนี้ เราจะเรียนรู้วิธีการแก้ปัญหาต่อไปนี้:

ข้อความปัญหา — กำหนดตัวเลข n ให้พิมพ์เลขเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ n โดยที่ n เป็นตัวเลขขนาดเล็ก

มาเปลี่ยนดูโค้ดตัวอย่างด้านล่างนี้:

ตัวอย่างโค้ด

def SieveOfEratosthenes(n):
    # สร้างอาร์เรย์บูลีนที่มีค่า True ทั้งหมด
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
        # หากค่าไม่เปลี่ยนแปลง แสดงว่าเป็นเลขเฉพาะ
        if (prime[p] == True):
            # อัปเดตตัวคูณทั้งหมดให้เป็น False
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 1
    prime[0] = False
    prime[1] = False
    # แสดงผล
    for p in range(n + 1):
        if prime[p]:
            print(p, end=" ")

if __name__ == '__main__':
    n = 33
    print("เลขเฉพาะที่น้อยกว่าหรือเท่ากับ", n, "คือ")
    SieveOfEratosthenes(n)

ผลลัพธ์

เลขเฉพาะที่น้อยกว่าหรือเท่ากับ 33 คือ 2 3 5 7 11 13 17 19 23 29 31

ตัวแปรทั้งหมดถูกประกาศในขอบเขตท้องถิ่น (local scope) และการอ้างอิงของมันแสดงในรูปภาพด้านบน

สรุป

ในบทความนี้ เราได้เรียนรู้วิธีการเขียนโปรแกรม Python สำหรับการคัดกรองเอราโธสเธนีส เพื่อหาเลขเฉพาะได้อย่างมีประสิทธิภาพ