จำนวนเฉพาะ

ในคณิตศาสตร์ จำนวนเฉพาะ  คือ จำนวนเต็มบวกที่มากกว่า 1 และมีตัวหารที่เป็นบวกอยู่ 2 ตัว คือ 1 กับตัวมันเอง ตรงข้ามกับจำนวนประกอบ
ลำดับของจำนวนเฉพาะเริ่มต้นด้วย
 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, ... (ลำดับ #เปลี่ยนทาง 
ข้อมูลเมื่อ 2024[ [update]] จำนวนเฉพาะที่มากที่สุดเท่าที่มีการค้นพบซึ่งเป็นจำนวนเฉพาะแมร์แซนมีความยาว 41,024,320 หลัก
การแทนจำนวนธรรมชาติ ด้วยผลคูณของจำนวนเฉพาะ.
ทฤษฎีบทมูลฐานของเลขคณิตกล่าวว่า จำนวนเต็มบวกทุกตัวสามารถเขียนได้ในรูปผลคูณของจำนวนเฉพาะ และเขียนได้แบบเดียวเท่านั้น จำนวนเฉพาะเป็นเหมือน "บล็อกก่อสร้าง" ของจำนวนธรรมชาติ ตัวอย่างเช่น
<math>23244 = 2^2 \times 3 \times 13 \times 149</math>
ไม่ว่าเราจะแยกตัวประกอบของ 23244 แบบใดโดยไม่คำนึงถึงลำดับของตัวประกอบแล้ว มันก็จะไม่ต่างไปจากนี้
สมบัติมูลฐาน.
การมีอยู่นับไม่ถ้วน.
มีจำนวนเฉพาะอยู่มากมายนับไม่ถ้วน ข้อเท็จจริงนี้พร้อมบทพิสูจน์ปรากฏเป็นครั้งแรกในหนังสือ "Elements" โดยยุคลิด จึงได้ชื่อว่าทฤษฎีบทของยุคลิด
บทพิสูจน์ของยุคลิดนั้นเริ่มต้นโดยพิสูจน์ว่า รายการจำกัด <math>p_1, p_2, \dotsc, p_n</math> ของจำนวนเฉพาะใด ๆ จะมีจำนวนเฉพาะอื่นที่ไม่อยู่ในลำดับนี้ แนวคิดหลักของบทพิสูจน์นี้คือ คูณจำนวนเฉพาะ <math>p_1, p_2, \dotsc, p_n</math> ในรายการทุกตัวเข้าด้วยกัน แล้วบวกหนึ่งให้กับผลคูณที่ได้ ซึ่งจะได้เป็นจำนวนใหม่
 <math> N = p_1\cdot p_2\dotsb p_n + 1</math>
โดยทฤษฎีบทหลักมูลของเลขคณิต จะได้ว่าจำนวนนี้ต้องแยกตัวประกอบเป็นผลคูณของจำนวนเฉพาะได้
 <math> N = q_1 \cdot q_2 \dotsb q_m</math>
(<math>N</math> อาจะมีตัวประกอบเป็นจำนวนเฉพาะตัวเดียวหรือหลายตัวก็ได้ และตัวประกอบเฉพาะเหล่านั้นอาจซ้ำกันก็ได้) แต่เนื่องจากจำนวนเฉพาะใด ๆ ในรายการ <math>p_1, p_2, \dotsc, p_n</math> เมื่อนำไปหาร <math> N </math> แล้วจะหารไม่ลงตัวเสมอ ดังนั้น ตัวประกอบเฉพาะ <math> q_1, q_2 \dotsc, q_m</math> ของ <math> N </math> ต้องเป็นจำนวนเฉพาะอื่นนอกเหนือจากในรายการ <math>p_1, p_2, \dotsc, p_n</math> จึงทำให้ได้ทันทีว่า มีจำนวนเฉพาะอยู่เป็นอนันต์
นอกจากบทพิสูจน์ของยูคลิดแล้ว ยังมีบทพิสูจน์ว่าจำนวนเฉพาะมีเป็นอนันต์ในแบบอื่น ๆ อีก เช่น บทพิสูจน์ของออยเลอร์โดยใช้วิธีการทางคณิตวิเคราะห์ บทพิสูจน์ของคริสเตียน ก็อลท์บัคโดยอาศัยจำนวนแฟร์มา บทพิสูจน์เชิงทอพอโลยีของฮิลแลล ฟัวร์ทสเตนแบร์ก และบทพิสูจน์ของเอิร์นส์ คุมเมอร์
การหาจำนวนเฉพาะ.
ตะแกรงเอราทอสเทนีส และ ตะแกรงของ Atkin เป็นวิธีที่ใช้สร้างรายการจำนวนเฉพาะทั้งหมดตามจำนวนที่กำหนดอย่างรวดเร็ว
ในทางปฏิบัติ เราต้องการตรวจสอบว่าเลขที่กำหนดให้ว่าเป็นจำนวนเฉพาะหรือไม่ มากกว่าจะสร้างรายการจำนวนเฉพาะทั้งหมดขึ้นมา ซึ่งวิธีที่ทดสอบ จะให้คำตอบด้วยความน่าจะเป็น เราสามารถตรวจสอบเลขที่มีขนาดใหญ่ (มี 1 พันหลักขึ้นไป) ว่าเป็นจำนวนเฉพาะหรือไม่ได้อย่างรวดเร็ว โดยใช้การทดสอบความเป็นจำนวนเฉพาะด้วยความน่าจะเป็น (probabilistic primality tests) ซึ่งวิธีนี้ จะต้องทำการสุ่มตัวเลขขึ้นมาตัวหนึ่ง เรียกว่า "พยาน" (witness) และใช้สูตรที่เกี่ยวข้องกับพยาน และจำนวนเฉพาะ "N" ทำการทดสอบ หลังจากที่ทดสอบไปหลายรอบ เราจะตอบได้ว่า "N" เป็น "จำนวนประกอบอย่างแน่นอน" หรือ "N" "อาจเป็นจำนวนเฉพาะ" วิธีทดสอบไม่สามารถให้คำตอบได้ว่าเป็นจำนวนเฉพาะอย่างแน่นอนหรือไม่ การทดสอบบางครั้ง เมื่อใส่จำนวนประกอบลงไป ก็ให้คำตอบว่า "อาจเป็นจำนวนเฉพาะ" เสมอ ไม่ว่าจะเลือกพยานตัวใดก็ตาม จำนวนเหล่านี้เรียกว่า จำนวนเฉพาะเทียม (pseudoprimes) สำหรับการทดสอบ
การประยุกต์.
จำนวนเฉพาะที่มีขนาดใหญ่มาก (ใหญ่กว่า 10100) นำไปใช้ประโยชน์ในขั้นตอนวิธีเข้ารหัสลับแบบกุญแจสาธารณะ นอกจากนี้ยังใช้ในตารางแฮช (hash tables) และเครื่องสุ่มเลขเทียม