Trình tạo Số Nguyên tố Trực tuyến

Số nguyên tố là gì?

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ chia hết cho 1 và chính nó. Các số nguyên tố nhỏ nhất là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Số 2 là số nguyên tố chẵn duy nhất – tất cả các số chẵn khác đều chia hết cho hai.

Các số như 4 (= 2 × 2), 6 (= 2 × 3) hoặc 15 (= 3 × 5) không phải là số nguyên tố – chúng ta gọi chúng là số hợp số.

Trình tạo hoạt động như thế nào?

Để liệt kê tất cả các số nguyên tố trong một phạm vi, chúng tôi sử dụng Sàng Eratosthenes – một trong những thuật toán lâu đời và hiệu quả nhất, được nhà toán học Hy Lạp Eratosthenes xứ Cyrene mô tả vào khoảng năm 240 TCN.

Thuật toán này dần dần loại bỏ các bội số của mỗi số nguyên tố tìm được. Những gì còn lại là số nguyên tố. Toàn bộ quá trình tính toán diễn ra trực tiếp trong trình duyệt của bạn – không có dữ liệu nào được gửi đến máy chủ.

Để chọn ngẫu nhiên, trình tạo trước tiên xây dựng một danh sách tất cả các số nguyên tố trong phạm vi, sau đó chọn ngẫu nhiên số lượng yêu cầu từ danh sách đó bằng cách sử dụng bộ tạo an toàn về mặt mật mã (crypto.getRandomValues()).

Tính năng của trình tạo

• Tất cả số nguyên tố – liệt kê mọi số nguyên tố trong phạm vi đã cho (tối đa 10.000)
• Chọn ngẫu nhiên – chọn N số nguyên tố ngẫu nhiên từ phạm vi (thích hợp cho các phạm vi lớn)
• Sắp xếp – sắp xếp kết quả theo thứ tự tăng dần
• Dấu phân cách – chọn cách các số sẽ được phân tách khi sao chép
• Thiết lập nhanh – các phạm vi phổ biến nhất chỉ với một cú nhấp chuột

Số nguyên tố được sử dụng ở đâu?

Mật mã và bảo mật

Số nguyên tố là nền tảng của mật mã hiện đại. Các thuật toán như RSA hoạt động dựa trên nguyên tắc rằng việc tính tích của hai số nguyên tố lớn là dễ dàng, nhưng việc phân tích ngược thành các thừa số nguyên tố lại rất khó khăn về mặt tính toán.

• Mã hóa RSA – các khóa được tạo từ hai số nguyên tố lớn
• Diffie-Hellman – trao đổi khóa trên một modulo số nguyên tố
• Hàm băm – số nguyên tố là các hằng số ma thuật (SHA, MD5)

Toán học và khoa học

• Lý thuyết số – các khối xây dựng cơ bản của số nguyên
• Giả thuyết Goldbach – mọi số chẵn > 2 có thể được biểu thị dưới dạng tổng của hai số nguyên tố (chưa được chứng minh)
• Giả thuyết Riemann – một trong các bài toán của Hilbert, liên quan đến sự phân bố các số nguyên tố

Ứng dụng thực tế

• Bảng băm – kích thước bảng là một số nguyên tố giúp giảm xung đột
• Bộ tạo số giả ngẫu nhiên – đồng dư tuyến tính với một modulo số nguyên tố
• Âm nhạc và nhịp điệu – đa nhịp điệu với độ dài chu kỳ là số nguyên tố

Phân bố số nguyên tố

Các số nguyên tố được phân bố không đều giữa các số tự nhiên, nhưng mật độ của chúng giảm dần khi phạm vi tăng lên. Điều này được mô tả bởi Định lý số nguyên tố: số lượng số nguyên tố lên đến N xấp xỉ N / ln(N).

Sàng Eratosthenes từng bước

Phạm vi 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. Chọn 2, gạch bỏ các bội số: 4, 6, 8, 10, 12...
2. Chọn 3, gạch bỏ các bội số: 9, 15, 21, 27...
3. Chọn 5, gạch bỏ các bội số: 25...
4. √30 ≈ 5.5 → hoàn tất

Các số nguyên tố: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Sàng Eratosthenes trong mã

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

Câu hỏi thường gặp (FAQ)