ตะแกรงของเอราโตสเทนีส
แสดงจำนวนเฉพาะทั้งหมดถึง N ในเวลาเกือบเชิงเส้น
ตะแกรงของเอราโตสเทนีส เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
จำนวนเฉพาะจำนวนมาก
บางครั้งคุณต้องการจำนวนเฉพาะทุกจำนวนจนถึง N ไม่ใช่เพียงการตรวจสอบครั้งเดียว ตะแกรงเอราทอสเทเนสจะค้นหาจำนวนเหล่านั้นทั้งหมดในการกวาดครั้งเดียว 🧹
แนวคิดสำคัญ
เริ่มต้นด้วยการสมมติว่าทุกจำนวนเป็นจำนวนเฉพาะ จากนั้นขีดฆ่าพหุคูณของจำนวนเฉพาะแต่ละจำนวนที่พบ เหลือไว้เพียงจำนวนเฉพาะจริง
ตั้งค่าตัวบ่งชี้
สร้างรายการค่าบูลีน โดยให้ดัชนี i ระบุว่า i เป็นจำนวนเฉพาะหรือไม่ อาร์เรย์นี้คือพื้นที่ที่ตะแกรงใช้ทำงาน
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = Falseไล่ผ่านตัวเลือก
ไล่ค่า i เพิ่มขึ้นเรื่อย ๆ เมื่อพบครั้งแรกว่าตัวเลขหนึ่งยังมีตัวบ่งชี้เป็นจริง ตัวเลขนั้นต้องเป็นจำนวนเฉพาะใหม่ที่ไม่มีตัวประกอบที่เล็กกว่า
ขีดฆ่าพหุคูณ
สำหรับจำนวนเฉพาะแต่ละจำนวน i ให้ทำเครื่องหมาย 2i, 3i, 4i และต่อไปว่าไม่ใช่จำนวนเฉพาะ ค่าพหุคูณเหล่านั้นมี i เป็นตัวหารอย่างชัดเจน
for j in range(i * i, n + 1, i):
is_prime[j] = Falseเริ่มที่ i ยกกำลังสอง
เริ่มขีดฆ่าที่ i*i ไม่ใช่ 2i เพราะพหุคูณที่เล็กกว่าทั้งหมดถูกนำออกไปแล้วโดยจำนวนเฉพาะก่อนหน้า จึงข้ามไปได้
หยุดที่รากที่สอง
คุณต้องทำตะแกรงต่อไปตราบใดที่ i*i ยังน้อยกว่าหรือเท่ากับ N หลังผ่านรากที่สองแล้ว ตัวบ่งชี้ที่ยังเป็นจริงทั้งหมดก็เป็นจำนวนเฉพาะอยู่แล้ว
ตะแกรงทั้งหมด
รวมการสแกนรอบนอกเข้ากับการขีดฆ่าด้านใน หลังจบลูป ดัชนีทุกตัวที่ยังมีตัวบ่งชี้เป็นจริงจะเป็นจำนวนเฉพาะที่ยืนยันแล้ว
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = Falseรวบรวมจำนวนเฉพาะ
อ่านตัวบ่งชี้ที่เสร็จแล้วลงในรายการด้วยการสร้างรายการแบบย่อ ตอนนี้คุณมีจำนวนเฉพาะทุกจำนวนจนถึง N พร้อมใช้สำหรับคำถามที่ต้องการความรวดเร็วแล้ว
primes = [i for i, p in enumerate(is_prime) if p]เหตุใดจึงรวดเร็ว
ตะแกรงใช้เวลาประมาณ O(n log log n) ซึ่งเกือบเป็นเชิงเส้น นี่คือเหตุผลที่ตะแกรงทำงานได้ดีกว่าการทดสอบตัวเลขทีละจำนวนซ้ำ ๆ
ระวังการใช้หน่วยความจำ
อาร์เรย์ตัวบ่งชี้ใช้หน่วยความจำแปรผันตาม N สำหรับขอบเขตที่ใหญ่มาก โปรดตรวจสอบพื้นที่หน่วยความจำที่มีอยู่ก่อนจัดสรร
ตรวจสอบอย่างรวดเร็ว
ทบทวนการปรับปรุงเล็ก ๆ ในลูปด้านใน
สรุป
ตอนนี้คุณสามารถสร้างตะแกรงเพื่อแสดงรายการจำนวนเฉพาะทั้งหมดจนถึง N ในเวลาเกือบเชิงเส้น โดยเริ่มขีดฆ่าจำนวนเฉพาะแต่ละจำนวนที่ i*i และหยุดที่รากที่สองได้แล้ว ✅
คำถามที่พบบ่อย
บทเรียน “ตะแกรงของเอราโตสเทนีส” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ตะแกรงของเอราโตสเทนีส” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ตะแกรงของเอราโตสเทนีส”
แสดงจำนวนเฉพาะทั้งหมดถึง N ในเวลาเกือบเชิงเส้น คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “ตะแกรงของเอราโตสเทนีส” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- GCD, LCM และอัลกอริทึมยูคลิด
- การทดสอบจำนวนเฉพาะถึง sqrt(n)
- ตะแกรงของเอราโตสเทนีส
- การแยกตัวประกอบจำนวนเฉพาะและตัวหาร