Máy Tính Số Nguyên Tố

Máy Tính Số Nguyên Tố - Tổng, Đếm & Tìm Số Nguyên Tố

🔢 Tính tổng số nguyên tố, tìm số nguyên tố trong khoảng, kiểm tra số có phải số nguyên tố không, và tìm số nguyên tố thứ n. Thuật toán Sàng Eratosthenes nhanh kèm trực quan hóa.

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

Số nguyên tố là số tự nhiên lớn hơn 1 và không thể tạo được bằng cách nhân hai số tự nhiên nhỏ hơn. Nói cách khác, nó có đúng hai ước: 1 và chính nó.

25 số nguyên tố đầu tiên

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Cách kiểm tra một số có phải số nguyên tố không

Phương pháp 1 - Chia thử:

• Kiểm tra n có chia hết cho bất kỳ số nào từ 2 đến √n không
• Nếu có, đó là hợp số (không nguyên tố)
• Nếu không, đó là số nguyên tố

Ví dụ: 17 có phải số nguyên tố không?

• √17 ≈ 4.12, nên kiểm tra chia hết cho 2, 3, 4
• 17 ÷ 2 = 8.5 (không chia hết)
• 17 ÷ 3 = 5.67 (không chia hết)
• 17 ÷ 4 = 4.25 (không chia hết)
• Kết luận: 17 là số nguyên tố!

Sàng Eratosthenes

Thuật toán cổ điển để tìm tất cả số nguyên tố đến n:

• Bước 1: Liệt kê tất cả các số từ 2 đến n
• Bước 2: Đánh dấu 2 là số nguyên tố, gạch bỏ các bội của 2
• Bước 3: Tìm số chưa bị gạch tiếp theo (3), đánh dấu là số nguyên tố
• Bước 4: Gạch bỏ các bội của số nguyên tố đó
• Bước 5: Lặp lại đến √n
• Kết quả: Các số không bị gạch là số nguyên tố

Tổng các số nguyên tố

Tổng của n số nguyên tố đầu tiên:

• 10 số đầu: 2+3+5+7+11+13+17+19+23+29 = 129
• 100 số đầu: Tổng = 24.133
• 1000 số đầu: Tổng = 3.682.913

Tổng các số nguyên tố đến n:

• Đến 10: 2+3+5+7 = 17
• Đến 100: Tổng = 1.060
• Đến 1000: Tổng = 76.127

Định lý số nguyên tố

Số lượng số nguyên tố nhỏ hơn n xấp xỉ bằng n/ln(n):

• Đến 100: ~25 số (thực tế: 25)
• Đến 1.000: ~145 số (thực tế: 168)
• Đến 10.000: ~1.086 số (thực tế: 1.229)
• Đến 100.000: ~8.686 số (thực tế: 9.592)

Các loại số nguyên tố

Nguyên tố sinh đôi: hai số nguyên tố chênh nhau 2

• (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)...

Nguyên tố Mersenne: dạng 2ᵖ - 1 với p là số nguyên tố

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• Số nguyên tố lớn nhất đã biết là Mersenne (24,8 triệu chữ số!)

Nguyên tố Sophie Germain: số nguyên tố p sao cho 2p+1 cũng là nguyên tố

• 2 (2×2+1 = 5), 3 (2×3+1 = 7), 5 (2×5+1 = 11), 11, 23, 29...

Nguyên tố Fermat: dạng 2^(2ⁿ) + 1

• F₀ = 3, F₁ = 5, F₂ = 17, F₃ = 257, F₄ = 65.537
• Chỉ có 5 số nguyên tố Fermat đã biết

Ứng dụng của số nguyên tố

Mật mã học (RSA):

• Dựa trên độ khó phân tích thừa số các số lớn
• Dùng hai số nguyên tố lớn (hàng trăm chữ số)
• Bảo mật ngân hàng trực tuyến, email, website

Bảng băm (Hash tables):

• Kích thước bảng băm là số nguyên tố giúp giảm va chạm
• Dùng trong cơ sở dữ liệu và bộ nhớ đệm

Tạo số ngẫu nhiên:

• Số nguyên tố giúp tạo dãy giả ngẫu nhiên tốt hơn
• Dùng trong mô phỏng và trò chơi

Sự thật thú vị về số nguyên tố

• Vô hạn: Euclid (~300 TCN) đã chứng minh số nguyên tố là vô hạn
• Khoảng trống: có thể rất lớn (không có số nguyên tố trong hàng triệu số liên tiếp)
• Giả thuyết Goldbach: mọi số chẵn > 2 là tổng của hai số nguyên tố (chưa chứng minh!)
• Giả thuyết Riemann: bài toán nổi tiếng về phân bố số nguyên tố
• Khoảng cách nguyên tố: chênh lệch giữa các số nguyên tố liên tiếp thường tăng
• Xác suất: số ngẫu nhiên n có ~1/ln(n) cơ hội là số nguyên tố

Kỷ lục số nguyên tố

• Số nguyên tố lớn nhất đã biết: 2^82,589,933 - 1 (phát hiện năm 2018, 24.862.048 chữ số)
• Cặp nguyên tố sinh đôi lớn nhất: 2.996.863.034.895 × 2^1.290.000 ± 1
• Tính toán: GIMPS (Great Internet Mersenne Prime Search) dự án tính toán phân tán

Nhầm lẫn phổ biến

• 1 KHÔNG phải số nguyên tố: theo định nghĩa hiện đại (cần đúng 2 ước)
• Không phải số lẻ nào cũng là nguyên tố: 9, 15, 21, 25... là hợp số
• Công thức cho mọi số nguyên tố: không có công thức đơn giản tạo ra tất cả số nguyên tố
• Mẫu trong số nguyên tố: không có quy luật dự đoán được (trông như ngẫu nhiên)

💡 Mẹo: khi kiểm tra một số lớn có phải số nguyên tố không, bạn chỉ cần thử chia đến căn bậc hai của nó! Ví dụ, để kiểm tra 997, chỉ cần thử đến √997 ≈ 31,6: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31. Nếu không số nào chia hết 997 thì 997 là số nguyên tố! Ngoài ra, trừ 2 và 3, mọi số nguyên tố đều có dạng 6k±1, điều này có thể giúp tăng tốc việc tìm kiếm.