เครื่องกำเนิดจำนวนเฉพาะออนไลน์

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

จำนวนเฉพาะ คือจำนวนธรรมชาติที่มากกว่า 1 ซึ่งหารลงตัวด้วย 1 และตัวมันเองเท่านั้น จำนวนเฉพาะที่น้อยที่สุดคือ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… เลข 2 เป็นจำนวนเฉพาะคู่เพียงตัวเดียว – จำนวนคู่ที่เหลือทั้งหมดหารด้วยสองลงตัว

ตัวเลขเช่น 4 (= 2 × 2), 6 (= 2 × 3) หรือ 15 (= 3 × 5) ไม่ใช่ จำนวนเฉพาะ – เราเรียกว่าจำนวนประกอบ

เครื่องกำเนิดนี้ทำงานอย่างไร?

สำหรับการแสดงจำนวนเฉพาะทั้งหมดในช่วง เราใช้ ตะแกรงของเอราทอสเทนีส (Sieve of Eratosthenes) ซึ่งเป็นหนึ่งในอัลกอริทึมที่เก่าแก่และมีประสิทธิภาพที่สุด อธิบายโดยนักคณิตศาสตร์ชาวกรีก Eratosthenes แห่ง Cyrene ประมาณ 240 ปีก่อนคริสตกาล

อัลกอริทึมจะค่อยๆ ขีดฆ่าพหุคูณของจำนวนเฉพาะที่พบแต่ละตัว สิ่งที่เหลืออยู่คือจำนวนเฉพาะ การคำนวณทั้งหมดจะเกิดขึ้น โดยตรงในเบราว์เซอร์ของคุณ – ไม่มีการส่งข้อมูลไปยังเซิร์ฟเวอร์

สำหรับการเลือกแบบสุ่ม เครื่องกำเนิดจะสร้างรายการจำนวนเฉพาะทั้งหมดในช่วงก่อน จากนั้นจะสุ่มเลือกจำนวนที่ต้องการโดยใช้เครื่องกำเนิดที่ปลอดภัยทางคณิตศาสตร์ (crypto.getRandomValues())

คุณสมบัติของเครื่องกำเนิด

• จำนวนเฉพาะทั้งหมด – แสดงจำนวนเฉพาะทุกตัวในช่วงที่กำหนด (สูงสุด 10,000)
• การเลือกแบบสุ่ม – เลือกจำนวนเฉพาะ N ตัวแบบสุ่มจากช่วง (เหมาะสำหรับช่วงขนาดใหญ่)
• การเรียงลำดับ – จัดเรียงผลลัพธ์จากน้อยไปมาก
• ตัวคั่น – เลือกวิธีที่ตัวเลขจะถูกคั่นเมื่อคัดลอก
• การตั้งค่าล่วงหน้าด่วน – ช่วงที่ใช้บ่อยที่สุดด้วยการคลิกเพียงครั้งเดียว

จำนวนเฉพาะถูกใช้ที่ไหนบ้าง?

การเข้ารหัสและความปลอดภัย

จำนวนเฉพาะเป็นพื้นฐานของการเข้ารหัสสมัยใหม่ อัลกอริทึมเช่น RSA ทำงานบนหลักการที่ว่าการคำนวณผลคูณของจำนวนเฉพาะขนาดใหญ่สองตัวนั้นง่าย แต่การแยกตัวประกอบกลับไปเป็นจำนวนเฉพาะเดิมนั้นยากมากในเชิงคำนวณ

• การเข้ารหัส RSA – คีย์ถูกสร้างจากจำนวนเฉพาะขนาดใหญ่สองตัว
• Diffie-Hellman – การแลกเปลี่ยนคีย์บนโมดูลาร์จำนวนเฉพาะ
• ฟังก์ชันแฮช – จำนวนเฉพาะเป็นค่าคงที่วิเศษ (SHA, MD5)

คณิตศาสตร์และวิทยาศาสตร์

• ทฤษฎีจำนวน – องค์ประกอบพื้นฐานของจำนวนเต็ม
• ข้อความคาดการณ์ของโกลด์บาค – ทุกจำนวนคู่ที่ > 2 สามารถเขียนเป็นผลรวมของจำนวนเฉพาะสองตัวได้ (ยังไม่ได้รับการพิสูจน์)
• สมมติฐานของรีมันน์ – หนึ่งในปัญหาของฮิลเบิร์ตที่เกี่ยวข้องกับการกระจายตัวของจำนวนเฉพาะ

การใช้งานจริง

• ตารางแฮช – ขนาดของตารางที่เป็นจำนวนเฉพาะช่วยลดการชนกัน
• เครื่องกำเนิดตัวเลขสุ่มเทียม – การ congruence เชิงเส้นพร้อมโมดูลาร์จำนวนเฉพาะ
• ดนตรีและจังหวะ – polyrhythm ที่มีความยาวรอบเป็นจำนวนเฉพาะ

การกระจายตัวของจำนวนเฉพาะ

จำนวนเฉพาะมีการกระจายตัวไม่สม่ำเสมอในหมู่จำนวนธรรมชาติ แต่ความหนาแน่นของมันลดลงเมื่อช่วงขยายใหญ่ขึ้น นี่คือสิ่งที่ ทฤษฎีบทจำนวนเฉพาะ อธิบาย: จำนวนของจำนวนเฉพาะที่น้อยกว่าหรือเท่ากับ N ประมาณ N / ln(N)

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

ช่วง 2–30:
[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]

1. เลือก 2, ขีดฆ่าพหุคูณ: 4, 6, 8, 10, 12...
2. เลือก 3, ขีดฆ่าพหุคูณ: 9, 15, 21, 27...
3. เลือก 5, ขีดฆ่าพหุคูณ: 25...
4. √30 ≈ 5.5 → เสร็จสิ้น

จำนวนเฉพาะ: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

ตะแกรงของเอราทอสเทนีสในโค้ด

JavaScript

function sieve(to) {
  const composite = new Uint8Array(to + 1);
  const primes = [];
  for (let p = 2; p <= to; p++) {
    if (composite[p]) continue;
    primes.push(p);
    for (let j = p * p; j <= to; j += p) composite[j] = 1;
  }
  return primes;
}

Python

def sieve(n):
    composite = bytearray(n + 1)
    primes = []
    for p in range(2, n + 1):
        if not composite[p]:
            primes.append(p)
            for j in range(p * p, n + 1, p):
                composite[j] = 1
    return primes

คำถามที่พบบ่อย (FAQ)