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

ในวิชาคณิตศาสตร์ ตะแกรงของเอราทอสเทนีส (อังกฤษ: Sieve of Eratosthenes) เป็นขั้นตอนวิธีที่ง่ายและเก่าแก่สำหรับการค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าขีดจำกัดที่กำหนดใด ๆ

ตะแกรงของเอราทอสเทนีส: ขั้นตอนวิธีสำหรับจำนวนเฉพาะค่าต่ำกว่า 121 (เพิ่มประสิทธิภาพโดยการเริ่มต้นจากกำลังสองของจำนวนเฉพาะแต่ละตัว)

กระบวนการของขั้นตอนวิธี เป็นการค่อย ๆ ตัดจำนวนที่เป็นจำนวนประกอบ (นั่นคือไม่ใช่จำนวนเฉพาะ)ออก โดยการไล่ตัดพหุคูณของจำนวนเฉพาะแต่ละตัวตั้งแต่ 2 ขึ้นไป ซึ่งชุดพหุคูณของจำนวนเฉพาะใด ๆ สร้างได้จากลำดับของตัวเลขที่เริ่มจากจำนวนเฉพาะนั้นและมีผลต่างคงที่เท่ากับจำนวนเฉพาะนั้น กระบวนการไล่แบบนี้นี้เป็นความแตกต่างระหว่างวิธีตะแกรงกับวิธีการหารเชิงทดลอง

หลักฐานเก่าแก่ที่สุดของวิธีตะแกรงของเอราทอสเทนีส (กรีกโบราณ: κόσκινον Ἐρατοσθένους, kóskinon Eratosthénous) อยู่ในหนังสือเลขคณิตเบื้องต้นของนิโคมาคัส ซึ่งอธิบายและระบุที่มาจากเอราทอสเทนีสนักคณิตศาสตร์ชาวกรีก

ภาพรวม

จำนวนเฉพาะ คือ จำนวนธรรมชาติ ที่มีตัวหารเป็นจำนวนธรรมชาติแตกต่างกันสองตัว ได้แก่ 1 และตัวมันเอง

วิธีการค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับจำนวนเต็ม n โดยวิธีเอราทอสเทนีส ทำได้ดังนี้

1. สร้างรายการของจำนวนเต็มตั้งแต่ 2 ถึง n : (2, 3, 4, ..., n )
2. เริ่มแรกให้ p เท่ากับ 2 ซึ่งเป็นจำนวนเฉพาะจำนวนน้อยที่สุด
3. ไล่พหุคูณของ p โดยการนับเพิ่มทีละ p จาก 2p ไปจนเลยขีดจำกัด n และทำเครื่องหมายไว้ในรายการ (จำนวนเหล่านี้จะมี 2p 3p 4p, ... ไปเรื่อย ๆ ; ตัว p เองไม่ต้องทำเครื่องหมาย)
4. หาจำนวนตัวแรกที่มากกว่า p ในรายการที่ไม่ได้ทำเครื่องหมาย หากไม่มีหมายเลขดังกล่าว ขั้นตอนวิธีจะเสร็จสิ้น มิฉะนั้นให้ p เท่ากับจำนวนใหม่นี้ (ซึ่งเป็นจำนวนเฉพาะถัดไป) และทำซ้ำจากขั้นตอนที่ 3
5. เมื่อขั้นตอนวิธีสิ้นสุดลง จำนวนที่เหลืออยู่ที่ไม่ได้ทำเครื่องหมายในรายการ จะเป็นจำนวนเฉพาะทั้งหมดที่น้อยกว่า n

แนวคิดหลักของขั้นตอนวิธีนี้ คือค่า p ทุกตัวจะเป็นจำนวนเฉพาะ เพราะจำนวนประกอบจะถูกทำเครื่องหมายว่าเป็นพหุคูณของจำนวนเฉพาะที่เล็กกว่า สังเกตว่าบางหมายเลขอาจมีการทำเครื่องหมายมากกว่าหนึ่งครั้ง (เช่น 15 จะถูกทำเครื่องหมายทั้งในการไล่พหุคูณของ 3 และของ 5)

เพื่อเพิ่มประสิทธิภาพ เราสามารถเริ่มทำเครื่องหมายตัวเลขในขั้นตอนที่ 3 จาก p² เนื่องจากพหุคูณที่น้อยกว่านี้จะทำเครื่องหมายไปแล้ว ซึ่งหมายความว่าขั้นตอนวิธีสามารถจะยุติในขั้นตอนที่ 4 หาก p² มากกว่า n

การเพิ่มประสิทธิภาพอีกประการ คือการทำขั้นแรกโดยไล่เฉพาะเลขคี่เท่านั้น (3, 5, ..., n), แล้วนับเพิ่มทีละ 2p ในขั้นตอนที่ 3 เพื่อทำเครื่องหมายเฉพาะพหุคูณคี่

ตัวอย่าง

หากต้องการค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าหรือเท่ากับ 30 ให้ดำเนินการดังนี้

ขั้นแรกสร้างรายการจำนวนเต็มตั้งแต่ 2 ถึง 30:

${\displaystyle {\begin{aligned}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{aligned}}}$ 

จำนวนแรกในรายการคือ 2 ไล่ตัดจำนวนในรายการหลังจาก 2 โดยนับเรื่มจาก 2 เพิ่มไปทีละ 2 (จำนวนเหล่านี้จะเป็นพหุคูณทั้งหมดของ 2 ในรายการ):

${\displaystyle {\begin{aligned}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{aligned}}}$ 

จำนวนถัดไปในรายการหลังจาก 2 คือ 3 ไล่ตัดจำนวนในรายการหลังจาก 3 โดยนับจาก 3 เพิ่มไปทีละ 3 (จำนวนเหล่านี้จะเป็นทวีคูณทั้งหมดของ 3 ในรายการ):

${\displaystyle {\begin{aligned}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{aligned}}}$ 

จำนวนถัดไปในรายการหลังจาก 3 คือ 5 ไล่ตัดจำนวนในรายการหลังจาก 5 โดยนับจาก 5 เพิ่มไปทีละ 5 (จำนวนเหล่านี้จะเป็นทวีคูณทั้งหมดของ 5 ในรายการ):

${\displaystyle {\begin{aligned}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{aligned}}}$ 

จำนวนถัดไปในรายการหลังจาก 5 คือ 7 ดังนั้นขั้นถัดไปคือการไล่ตัดจำนวนในรายการหลังจาก 7 โดยนับจาก 7 เพิ่มไปทีละ 7 แต่จำนวนเหล่านี้ (14, 21, 28) ถูกตัดออกไปหมดแล้ว เนื่องจากเป็นพหุคูณของจำนวนเฉพาะที่เล็กกว่า เห็นได้จากการที่ 7 × 7 > 30 จำนวนทั้งหมดที่เหลือจึงเป็นจำนวนเฉพาะที่น้อยกว่า 30:

${\displaystyle {\begin{aligned}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{aligned}}}$ 

อ้างอิง

1. Horsley, Rev. Samuel, F. R. S., "Κόσκινον Ερατοσθένους or, The Sieve of Eratosthenes. Being an account of his method of finding all the Prime Numbers," Philosophical Transactions (1683–1775), Vol. 62. (1772), pp. 327–347.
2. O'Neill, Melissa E., "The Genuine Sieve of Eratosthenes", Journal of Functional Programming, published online by Cambridge University Press 9 October 2008 doi:10.1017/S0956796808007004, pp. 10, 11 (contains two incremental sieves in Haskell: a priority-queue–based one by O'Neill and a list–based, by Richard Bird).
3. Hoche, Richard, บ.ก. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, Leipzig: B.G. Teubner, p. 31