Phân tích ra thừa số nguyên tố
Phân tích một số nguyên ra thừa số nguyên tố, liệt kê các ước của nó và kiểm tra xem nó có phải số nguyên tố không.
Chạy hoàn toàn trong trình duyệt của bạn. Không có gì được tải lên, ghi log hay lưu trữ.
Phân tích ra thừa số nguyên tố
2^3 × 3^2 × 5
- Là số nguyên tố?
- không
- Các thừa số nguyên tố khác nhau
- 3
- Số lượng ước
- 24
- Các ước
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
Mọi số nguyên lớn hơn 1 đều là tích của các số nguyên tố, và với mỗi số chỉ có một tích như vậy: đó là định lý cơ bản của số học. Công cụ này tìm ra tích đó, cùng mọi thứ suy ra từ nó: số đó có bao nhiêu ước và đó là những ước nào.
Cách hoạt động
Phép chia thử, với một lối tắt: sau khi đã loại 2 và 3, mọi số nguyên tố còn lại đều nằm ngay bên này hoặc bên kia một bội của sáu, nên các ứng viên tăng theo bước sáu thay vì bước hai. Phần còn lại sau khi sàng là số nguyên tố và được thêm vào làm thừa số cuối cùng.
Các ước được xây dựng từ kết quả phân tích chứ không phải bằng cách thử mọi số đến n. Một số viết dưới dạng 2³ × 3² × 5 có (3+1) × (2+1) × (1+1) = 24 ước, và mỗi ước là một lựa chọn lấy bao nhiêu thừa số của mỗi số nguyên tố, nên một khi đã biết kết quả phân tích thì việc liệt kê chúng không tốn gì.
Giới hạn là một nghìn tỷ. Phép chia thử chỉ đi tối đa đến căn bậc hai của số đó, ở mức này là một triệu bước: nhanh. Vượt quá mức đó, một số tình cờ là tích của hai số nguyên tố lớn sẽ khiến trang tải mất cả phút, nên trang từ chối.
Ví dụ
| Trường hợp | Dữ liệu nhập | Kết quả |
|---|---|---|
| Một số có nhiều ước | 360 | 2³ × 3² × 5: 24 ước |
| Một số nguyên tố | 97 | 97: số nguyên tố, 2 ước |
| Một lũy thừa của hai | 1024 | 2¹⁰: 11 ước |
Câu hỏi thường gặp
Vì sao bắt đầu từ 2 mà không phải từ 1?
Vì 1 không có phân tích ra thừa số nguyên tố, và gọi nó là số nguyên tố sẽ phá vỡ tính duy nhất mà cả chủ đề này dựa vào: nếu 1 là số nguyên tố, 6 sẽ là 2 × 3, và 1 × 2 × 3, và 1 × 1 × 2 × 3, và sẽ không còn một đáp án duy nhất. Số 0 còn tệ hơn: mọi số đều chia hết nó.
Một số có bao nhiêu ước?
Cộng thêm một vào mỗi số mũ trong kết quả phân tích rồi nhân lại. 360 là 2³ × 3² × 5, nên 4 × 3 × 2 = 24. Một số nguyên tố có 2 ước — chính nó và 1 — và một số chính phương luôn có số ước là số lẻ, vì một trong các ước tự ghép cặp với chính nó.
Vì sao có giới hạn?
Phép chia thử chính xác và nhanh cho đến khi nó không còn nhanh nữa. Trường hợp xấu nhất là tích của hai số nguyên tố gần căn bậc hai, và giới hạn ở đây được đặt ở mức mà trường hợp đó vẫn trả về kết quả trong thời gian tải một trang. Một lời từ chối cho bạn biết chuyện gì đã xảy ra; một lần hết thời gian chờ thì không cho biết gì cả.
Đây có phải là cách người ta bẻ khóa mã hóa không?
Không, và đó chính là điểm mấu chốt. RSA dựa vào độ khó của việc phân tích một số có vài trăm chữ số; phép chia thử trên một số như thế sẽ kéo dài lâu hơn cả tuổi của vũ trụ. Những phương pháp tốt hơn có tồn tại nhưng vẫn còn xa mới đạt được, và đó là lý do cơ chế này hoạt động.
Cần biết
- Các ước được liệt kê đầy đủ nếu có tối đa sáu mươi tư ước; vượt quá mức đó chỉ hiển thị số lượng, vì một trang có chín trăm con số không phải thứ ai đó sẽ đọc.