รู้คำจำกัดความก่อน
จำนวนเฉพาะคือจำนวนเต็มที่มากกว่า 1 โดยมีตัวหารบวกสองตัวพอดี คือ 1 และตัวมันเอง จำนวนเฉพาะตัวแรกคือ 2, 3, 5, 7, 11 และ 13 จำนวน 1 ไม่ใช่จำนวนเฉพาะหรือจำนวนประกอบ และ 2 เป็นจำนวนเฉพาะคู่เท่านั้น
ตรวจสอบจนถึงรากที่สองเท่านั้น
หากต้องการทดสอบจำนวนเต็มบวก n คุณไม่จำเป็นต้องลองทุกจำนวนที่อยู่ต่ำกว่า n ถ้า n มีตัวประกอบที่ใหญ่กว่ารากที่สองของมัน ก็จะต้องมีตัวประกอบที่ตรงกันซึ่งเล็กกว่ารากที่สองด้วย ดังนั้นการทดสอบตัวหารที่เป็นไปได้จนถึงรากที่สองก็เพียงพอแล้ว
- ถ้าจำนวนน้อยกว่า 2 ก็ไม่ใช่จำนวนเฉพาะ
- ตรวจสอบว่าหารด้วย 2 ลงตัวหรือไม่ หากเป็นจำนวนคู่และมากกว่า 2 แสดงว่าไม่ใช่จำนวนเฉพาะ
- ลองตัวหารคี่ตั้งแต่ 3 จนถึงรากที่สอง ถ้าตัวใดตัวหนึ่งหารเท่ากัน แสดงว่าจำนวนนั้นประกอบกัน
- ถ้าไม่มีใครหารเท่ากัน แสดงว่าจำนวนนั้นเป็นจำนวนเฉพาะ
ตัวอย่าง: 97 เป็นจำนวนเฉพาะใช่หรือไม่
รากที่สองของ 97 น้อยกว่า 10 เล็กน้อย ตรวจสอบตัวหารเฉพาะที่เป็นไปได้จนถึงจุดนั้น: 2, 3, 5 และ 7 จำนวนนี้ไม่สามารถหารด้วยตัวใดตัวหนึ่งลงตัวได้ ดังนั้น 97 จึงเป็นจำนวนเฉพาะ
สำหรับ 91 เช็คจะพบว่า 7: 91 ÷ 7 = 13 ซึ่งเพียงพอที่จะแสดงว่า 91 เป็นแบบประกอบ ไม่จำเป็นต้องทดสอบตัวหารที่ใหญ่กว่า
ข้อผิดพลาดทั่วไป
- กำลังเรียก 1 ไพรม์ จำนวนเฉพาะต้องมีตัวหารบวกสองตัวพอดี ในขณะที่ 1 มีเพียงตัวเดียวเท่านั้น
- สมมุติว่าเลขคี่ทุกตัวเป็นจำนวนเฉพาะ วัสดุผสมที่เป็นเลขคี่ เช่น 9, 15, 21 และ 91 มีตัวหารเป็นเลขคี่
- ทดสอบตัวหารเล็กๆ เพียงไม่กี่ตัวเพื่อให้ได้จำนวนที่มาก การตรวจสอบจะต้องครอบคลุมตัวหารที่เป็นไปได้ทุกตัวจนถึงรากที่สอง หรือใช้อัลกอริทึมลำดับแรกที่ได้รับการตรวจสอบแล้ว
UsefulVerse ตรวจสอบอินพุตจำนวนเต็มที่ใช้งานจริงในเบราว์เซอร์ของคุณ ผลลัพธ์ที่สำคัญคือการตรวจสอบการหาร ไม่ใช่การพิสูจน์เกี่ยวกับคีย์การเข้ารหัสหรือการทดแทนซอฟต์แวร์ทฤษฎีตัวเลขเฉพาะทาง