Máy tính phân tích thừa số nguyên tố
Nhập số nguyên để viết dưới dạng tích các số nguyên tố, ví dụ 360 = 2³ × 3² × 5.
Kết quả
2³ × 3² × 5Phân tích thừa số nguyên tố
- Số thừa số nguyên tố khác nhau
- 3
- 2 xuất hiện 3 lần
- 3 xuất hiện 2 lần
- 5 xuất hiện 1 lần
Dữ liệu đầu vào
- Số nguyên
- 360
Cách tính
Chia cho 2 đến khi không thể, sau đó thử 3, 5, 7… (tối đa 100.000).
Kết quả
Phân tích thừa số nguyên tố
- Số thừa số nguyên tố khác nhau
- 3
Cách tính
- Chia cho 2 đến khi không thể, sau đó thử 3, 5, 7… (tối đa 100.000).
- Nếu phần dư lớn là hợp số, tìm thừa số bằng phương pháp rho Pollard.
- Kiểm tra từng thừa số bằng phép thử nguyên tố Miller–Rabin.
- Thời gian tính toán có giới hạn; công cụ sẽ báo nếu không đủ thời gian.
Ví dụ
360 = 2 × 180 = 2 × 2 × 90 = … = 2³ × 3² × 5.
Điều cần biết
- Tối đa 30 chữ số. Tích của hai số nguyên tố rất lớn có thể bị từ chối.
- Trên khoảng 25 chữ số, thừa số nguyên tố chỉ được ghi là “có khả năng nguyên tố”, chưa được chứng minh.
Khi nào nên dùng
- Dùng thừa số nguyên tố để rút gọn phân số hoặc tìm BCNN.
- Kiểm tra một số có phải số nguyên tố không.
Câu hỏi thường gặp
Phân tích thừa số nguyên tố là gì?
Đó là viết số nguyên thành tích các số nguyên tố, chẳng hạn 360 = 2³ × 3² × 5.
Máy tính tìm các thừa số như thế nào?
Công cụ thử các số nguyên tố nhỏ trước, sau đó dùng thuật toán tìm thừa số và phép thử nguyên tố cho phần dư lớn.
Thừa số rất lớn có luôn được chứng minh là số nguyên tố không?
Không phải lúc nào cũng vậy. Với thừa số rất lớn, kết quả Miller–Rabin có thể chỉ cho biết “có khả năng nguyên tố”, chưa phải chứng minh hình thức.