ตะแกรงของเอราทอสเทนีส

ในวิชาคณิตศาสตร์ ตะแกรงของเอราทอสเทนีส (Sieve of Eratosthenes) เป็นขั้นตอนวิธีที่ง่ายและเก่าแก่สำหรับการค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าขีดจำกัดที่กำหนดใด ๆ
กระบวนการของขั้นตอนวิธี เป็นการค่อย ๆ ตัดจำนวนที่เป็นจำนวนประกอบ (นั่นคือไม่ใช่จำนวนเฉพาะ)ออก โดยการไล่ตัดพหุคูณของจำนวนเฉพาะแต่ละตัวตั้งแต่ 2 ขึ้นไป ซึ่งชุดพหุคูณของจำนวนเฉพาะใด ๆ สร้างได้จากลำดับของตัวเลขที่เริ่มจากจำนวนเฉพาะนั้นและมีผลต่างคงที่เท่ากับจำนวนเฉพาะนั้น  กระบวนการไล่แบบนี้นี้เป็นความแตกต่างระหว่างวิธีตะแกรงกับวิธีการหารเชิงทดลอง
หลักฐานเก่าแก่ที่สุดของวิธีตะแกรงของเอราทอสเทนีส (κόσκινον Ἐρατοσθένους|kóskinon Eratosthénous) อยู่ในหนังสือเลขคณิตเบื้องต้นของนิโคมาคัส  ซึ่งอธิบายและระบุที่มาจากเอราทอสเทนีสนักคณิตศาสตร์ชาวกรีก
== ภาพรวม ==
จำนวนเฉพาะ คือ จำนวนธรรมชาติ ที่มีตัวหารเป็นจำนวนธรรมชาติแตกต่างกันสองตัว ได้แก่ 1 และตัวมันเอง
วิธีการค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับจำนวนเต็ม n โดยวิธีเอราทอสเทนีส ทำได้ดังนี้
สร้างรายการของจำนวนเต็มตั้งแต่ 2 ถึง n : (2, 3, 4, ..., n )
เริ่มแรกให้ p เท่ากับ 2 ซึ่งเป็นจำนวนเฉพาะจำนวนน้อยที่สุด
ไล่พหุคูณของ p โดยการนับเพิ่มทีละ p จาก 2p ไปจนเลยขีดจำกัด n และทำเครื่องหมายไว้ในรายการ (จำนวนเหล่านี้จะมี 2p 3p 4p, ... ไปเรื่อย ๆ ; ตัว p เองไม่ต้องทำเครื่องหมาย)
หาจำนวนตัวแรกที่มากกว่า p ในรายการที่ไม่ได้ทำเครื่องหมาย หากไม่มีหมายเลขดังกล่าว ขั้นตอนวิธีจะเสร็จสิ้น มิฉะนั้นให้ p เท่ากับจำนวนใหม่นี้ (ซึ่งเป็นจำนวนเฉพาะถัดไป) และทำซ้ำจากขั้นตอนที่ 3
เมื่อขั้นตอนวิธีสิ้นสุดลง จำนวนที่เหลืออยู่ที่ไม่ได้ทำเครื่องหมายในรายการ จะเป็นจำนวนเฉพาะทั้งหมดที่น้อยกว่า n
แนวคิดหลักของขั้นตอนวิธีนี้ คือค่า p ทุกตัวจะเป็นจำนวนเฉพาะ เพราะจำนวนประกอบจะถูกทำเครื่องหมายว่าเป็นพหุคูณของจำนวนเฉพาะที่เล็กกว่า สังเกตว่าบางหมายเลขอาจมีการทำเครื่องหมายมากกว่าหนึ่งครั้ง (เช่น 15 จะถูกทำเครื่องหมายทั้งในการไล่พหุคูณของ 3 และของ 5)
เพื่อเพิ่มประสิทธิภาพ เราสามารถเริ่มทำเครื่องหมายตัวเลขในขั้นตอนที่ 3 จาก p2 เนื่องจากพหุคูณที่น้อยกว่านี้จะทำเครื่องหมายไปแล้ว ซึ่งหมายความว่าขั้นตอนวิธีสามารถจะยุติในขั้นตอนที่ 4 หาก p2 มากกว่า n 
การเพิ่มประสิทธิภาพอีกประการ คือการทำขั้นแรกโดยไล่เฉพาะเลขคี่เท่านั้น (3, 5, ..., n), แล้วนับเพิ่มทีละ 2p ในขั้นตอนที่ 3 เพื่อทำเครื่องหมายเฉพาะพหุคูณคี่
=== ตัวอย่าง ===
หากต้องการค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ 30 ให้ดำเนินการดังนี้
ขั้นแรกสร้างรายการจำนวนเต็มตั้งแต่ 2 ถึง 30:
\begin{align}2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,\\
17,18,19,20,21,22,23,24,25,26,27,28,29,30\end{align}
จำนวนแรกในรายการคือ 2 ไล่ตัดจำนวนในรายการหลังจาก 2 โดยนับเรื่มจาก 2 เพิ่มไปทีละ 2 (จำนวนเหล่านี้จะเป็นพหุคูณทั้งหมดของ 2 ในรายการ):
\begin{align}2,3,\cancel{4},5,\cancel{6},7,\cancel{8},9,\cancel{10},11,\cancel{12},13,\cancel{14},15,\cancel{16},\\
17,\cancel{18},19,\cancel{20},21,\cancel{22},23,\cancel{24},25,\cancel{26},27,\cancel{28},29,\cancel{30}\end{align}
จำนวนถัดไปในรายการหลังจาก 2 คือ 3 ไล่ตัดจำนวนในรายการหลังจาก 3 โดยนับจาก 3 เพิ่มไปทีละ 3 (จำนวนเหล่านี้จะเป็นทวีคูณทั้งหมดของ 3 ในรายการ):
\begin{align}2,3,\cancel{4},5,\cancel{6},7,\cancel{8},\cancel{9},\cancel{10},11,\cancel{12},13,\cancel{14},\cancel{15},\cancel{16},\\
17,\cancel{18},19,\cancel{20},\cancel{21},\cancel{22},23,\cancel{24},25,\cancel{26},\cancel{27},\cancel{28},29,\cancel{30}
\end{align}
จำนวนถัดไปในรายการหลังจาก 3 คือ 5 ไล่ตัดจำนวนในรายการหลังจาก 5 โดยนับจาก 5 เพิ่มไปทีละ 5 (จำนวนเหล่านี้จะเป็นทวีคูณทั้งหมดของ 5 ในรายการ):
\begin{align}2,3,\cancel{4},5,\cancel{6},7,\cancel{8},\cancel{9},\cancel{10},11,\cancel{12},13,\cancel{14},\cancel{15},\cancel{16},\\
17,\cancel{18},19,\cancel{20},\cancel{21},\cancel{22},23,\cancel{24},\cancel{25},\cancel{26},\cancel{27},\cancel{28},29,\cancel{30}
\end{align}
จำนวนถัดไปในรายการหลังจาก 5 คือ 7 ดังนั้นขั้นถัดไปคือการไล่ตัดจำนวนในรายการหลังจาก 7 โดยนับจาก 7 เพิ่มไปทีละ 7 แต่จำนวนเหล่านี้ (14, 21, 28) ถูกตัดออกไปหมดแล้ว เนื่องจากเป็นพหุคูณของจำนวนเฉพาะที่เล็กกว่า เห็นได้จากการที่ 7 × 7 > 30 จำนวนทั้งหมดที่เหลือจึงเป็นจำนวนเฉพาะที่น้อยกว่า 30:
\begin{align}2,\  3, \qquad 5,\qquad 7,\qquad  \qquad 11,\qquad 13,\qquad \qquad \qquad \\
17,\qquad 19,\qquad \qquad \qquad 23,\qquad \qquad \qquad \qquad \qquad 29 \qquad
\end{align}
== อ้างอิง ==
ขั้นตอนวิธี
การทดสอบจำนวนเฉพาะ
Pages with unreviewed translations