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

right|frame| ตะแกรงของเอราทอสเทนีส: ขั้นตอนวิธีสำหรับจำนวนเฉพาะค่าต่ำกว่า 121 (เพิ่มประสิทธิภาพโดยการเริ่มต้นจากกำลังสองของจำนวนเฉพาะแต่ละตัว)
ในวิชาคณิตศาสตร์ **ตะแกรงของเอราทอสเทนีส** () เป็นขั้นตอนวิธีที่ง่ายและเก่าแก่สำหรับการค้นหาจำนวนเฉพาะทั้งหมดที่น้อยกว่าขีดจำกัดที่กำหนดใด ๆ 

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

หลักฐานเก่าแก่ที่สุดของวิธีตะแกรงของเอราทอสเทนีส () อยู่ในหนังสือเลขคณิตเบื้องต้นของนิโคมาคัส  ซึ่งอธิบายและระบุที่มาจากเอราทอสเทนีสนักคณิตศาสตร์ชาวกรีก 

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

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

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

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

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

การเพิ่มประสิทธิภาพอีกประการ คือการทำขั้นแรกโดยไล่เฉพาะเลขคี่เท่านั้น (3, 5, ..., *n*), แล้วนับเพิ่มทีละ 2*p* ในขั้นตอนที่ 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