เครื่องตรวจสอบจำนวนเฉพาะ (พร้อมการแยกตัว
ใส่จำนวนเต็มที่ไม่เป็นลบสูงสุด 10^18 เครื่องคำนวณทดสอบความเป็นจำนวนเฉพาะด้วย trial division และให้การแยกตัวประกอบเฉพาะสำหรับจำนวนประกอบ
- จำนวนเฉพาะก่อนหน้า
- 89
- จำนวนเฉพาะถัดไป
- 101
วิธีการทำงาน
จำนวนเฉพาะคืออะไร
จำนวนเฉพาะคือจำนวนธรรมชาติที่มากกว่า 1 ที่ไม่มีตัวหารบวกอื่นนอกจาก 1 และตัวเอง จำนวนเฉพาะสองสามตัวแรก: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 มันเป็น 'อะตอม' ของเลขคณิตจำนวนเต็ม — จำนวนเต็ม ≥ 2 ทุกจำนวนสามารถเขียนเป็นผลคูณของจำนวนเฉพาะได้อย่างไม่ซ้ำกัน (ทฤษฎีบทพื้นฐานของเลขคณิต)
1 ไม่ใช่จำนวนเฉพาะตามนิยาม 0 และจำนวนลบไม่ใช่จำนวนเฉพาะ 2 เป็นจำนวนเฉพาะคู่เดียว — จำนวนคู่อื่น ๆ ทุกจำนวนหารด้วย 2 ได้และเป็นจำนวนประกอบ
การทดสอบทำงานอย่างไร
เราใช้ trial division: ตรวจสอบการหารลงตัวด้วย 2 แล้ว 3 แล้ว 5, 7, 11, … ถึง √n ถ้าไม่มีตัวใดหารลงตัว n เป็นจำนวนเฉพาะ เราใช้การเพิ่มประสิทธิภาพ 6k±1 ที่ตรวจสอบเฉพาะผู้สมัครในรูปแบบ 6k+1 หรือ 6k−1 (เนื่องจากจำนวนเฉพาะทั้งหมด > 3 มีรูปแบบนี้) ลดจำนวนการทดสอบลง 2/3
Trial division เร็วสำหรับ n ถึง ~10^15 (ต่ำกว่าหนึ่งวินาที) เกินกว่านั้น ต้องการการทดสอบขั้นสูงอย่าง Miller-Rabin (แบบความน่าจะเป็น) หรือ AKS (แบบ deterministic) เราจำกัดที่ 10^18 เพื่อป้องกันเบราว์เซอร์ค้างสำหรับ input รุนแรง
ทำไมจำนวนเฉพาะจึงสำคัญ
การเข้ารหัส: การเข้ารหัส RSA คูณจำนวนเฉพาะ ~1,000 หลักสองตัวเพื่อผลิตตัวเลขที่ยากต่อการแยกตัวประกอบ ความปลอดภัยขึ้นอยู่กับความยากในการแยกตัวประกอบของจำนวนใหญ่ — ความท้าทายที่ศึกษามาหลายพันปี
การศึกษาคณิตศาสตร์: การแยกตัวประกอบเฉพาะเป็นพื้นฐาน แนวคิดอย่าง ห.ร.ม. ค.ร.น. arithmetic ปรวนแปร เศษส่วน และทฤษฎีจำนวนล้วนสร้างบนโครงสร้างตัวประกอบเฉพาะ
วิทยาการคอมพิวเตอร์: ขนาด hash table, เครื่องสร้างตัวเลขสุ่ม และอัลกอริทึมหลายอย่างใช้จำนวนเฉพาะสำหรับคุณสมบัติการหารที่โดดเด่น
คำถามที่พบบ่อย
›1 เป็นจำนวนเฉพาะไหม?
ไม่ 1 เป็น 'unit' ไม่ใช่จำนวนเฉพาะ จำนวนเฉพาะมีตัวหารบวกที่แตกต่างกันสองตัว (1 และตัวเอง) 1 มีเพียงตัวเดียว
›0 เป็นจำนวนเฉพาะไหม?
ไม่ จำนวนเฉพาะเป็นจำนวนเต็ม > 1
›2 เป็นจำนวนเฉพาะไหม?
ใช่ — 2 เป็นจำนวนเฉพาะคู่เดียว จำนวนคู่อื่น ๆ ทั้งหมดมี 2 เป็นตัวหารนอกจาก 1 และตัวเอง
›หาจำนวนเฉพาะถัดไปอย่างไร?
โดยเพิ่มจาก n+1 และทดสอบความเป็นจำนวนเฉพาะในแต่ละขั้น มีจำนวนเฉพาะเสมอภายใน n × ln(n) ของจำนวนใดก็ได้ ดังนั้นนี่สิ้นสุดอย่างรวดเร็วแม้สำหรับ input ขนาดใหญ่
›ทำไมสูงสุดถึง 10^18?
JavaScript BigInt รองรับใหญ่กว่า แต่ trial division ช้าลง 10^18 ปลอดภัยสำหรับการตรวจสอบ input ทั่วไปใน sub-second เกินกว่านั้น ใช้เครื่องมือเฉพาะทางอย่าง SymPy หรือ Mathematica
›ตรวจสอบจำนวนเฉพาะ 1,000 หลักได้ไหม?
ไม่ได้ด้วยเครื่องมือนี้ — trial division ช้าเกินไปในระดับนั้น การเข้ารหัสใช้การทดสอบ Miller-Rabin แบบความน่าจะเป็นสำหรับจำนวนเฉพาะ 1024 บิต (~300 หลัก)
›'Mersenne prime' คืออะไร?
จำนวนเฉพาะในรูปแบบ 2^p − 1 ณ ปี 2025 มีที่รู้จักเพียง 51 ตัว จำนวนเฉพาะที่ใหญ่ที่สุดที่รู้จัก (M82589933) เป็น Mersenne prime ที่มี ~25 ล้านหลัก
›ข้อมูลออกจากเบราว์เซอร์ไหม?
ไม่ การคำนวณทำงานในเครื่องของคุณ ไม่มีอะไรถูกส่งไปที่ server
เครื่องมือที่เกี่ยวข้อง
อัปเดตล่าสุด: