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

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

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

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

ภาพรวม

จำนวนเฉพาะ คือ จำนวนธรรมชาติ ที่มีตัวหารเป็นจำนวนธรรมชาติแตกต่างกันสองตัว ได้แก่ 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 จาก p² เนื่องจากพหุคูณที่น้อยกว่านี้จะทำเครื่องหมายไปแล้ว ซึ่งหมายความว่าขั้นตอนวิธีสามารถจะยุติในขั้นตอนที่ 4 หาก p² มากกว่า n ^[1]

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

ตัวอย่าง

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

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

${\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 ในรายการ):

${\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 ในรายการ):

${\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 ในรายการ):

${\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:

${\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.0 ^1.1 ^1.2 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.
↑ 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).
↑ Hoche, Richard, บ.ก. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, Leipzig: B.G. Teubner, p. 31

[horsley-1] 1.0 ^1.1 ^1.2 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.

[ONeill-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).

[nicomachus-3] Hoche, Richard, บ.ก. (1866), Nicomachi Geraseni Pythagorei Introductionis arithmeticae libri II, Leipzig: B.G. Teubner, p. 31

[1]

[2]

[3]