➗การตรวจสอบจำนวนเฉพาะ

จำนวนเฉพาะคืออะไร

จำนวนเฉพาะคือจำนวนเต็มที่มากกว่าหรือเท่ากับ 2 ที่ไม่มีตัวหารอื่นนอกจาก 1 และจำนวนนั้นเอง ตัวอย่างเช่น 2, 3, 5, 7, 11 เป็นจำนวนเฉพาะ และ 2 เป็นจำนวนเฉพาะเพียงจำนวนเดียวที่เป็นจำนวนคู่

1 เป็นจำนวนเฉพาะหรือไม่

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

วิธีระบุจำนวนเฉพาะ

เพื่อตรวจสอบว่าจำนวนเต็ม n เป็นจำนวนเฉพาะหรือไม่ คุณสามารถหารด้วยตัวเลขที่น้อยกว่าหรือเท่ากับ √n ตามลำดับ และหากไม่มีตัวเลขใดที่หารลงตัว n ก็เป็นจำนวนเฉพาะ ตัวอย่างเช่น 91 หารลงตัวด้วย 7 ซึ่งน้อยกว่า √91 (ประมาณ 9.5) ดังนั้น 91 จึงไม่ใช่จำนวนเฉพาะ

• วิธีการหารลองหา：วิธีการหารลองหาคือการหาร n ตามลำดับด้วยตัวเลขตั้งแต่ 2 ถึง √n เพื่อหาตัวหาร เมื่อจำนวนหลักมากขึ้น จำนวนการหารจะมากมายขึ้นอย่างมาก
• วิธีการทดสอบมิลเลอร์-ราบิน：วิธีการทดสอบมิลเลอร์-ราบินคือการใช้ตัวเลขหลายตัวเป็น "ฐาน" และตรวจสอบเศษเหลือของการยกกำลัง เพื่อค้นหาหลักฐานที่แสดงว่าตัวเลขไม่ใช่จำนวนเฉพาะ วิธีนี้สามารถตรวจสอบจำนวนขนาดใหญ่ได้ในเวลาสั้น