Máy tính phân tích thừa số nguyên tố
Viết một số thành tích của các số nguyên tố và thấy ngay liệu chính nó có phải số nguyên tố không.
Phân tích thừa số nguyên tố
Phân tích thừa số nguyên tố: 2³ × 3² × 5
- Viết đầy đủ
- 2 × 2 × 2 × 3 × 3 × 5
- Số ước
- 24
- Số nguyên tố kế tiếp
- 367
- Số nguyên tố liền trước
- 359
Số này là hợp số: nó có các ước khác 1 và chính nó.
| Số nguyên tố | Lũy thừa | Giá trị |
|---|---|---|
| 2 | 3 | 8 |
| 3 | 2 | 9 |
| 5 | 1 | 5 |
Cách hoạt động
Mọi số nguyên lớn hơn 1 đều là tích của các số nguyên tố theo đúng một cách, không kể thứ tự. Máy tính chia trước các số nguyên tố nhỏ, rồi dùng phương pháp Pollard rho để tách các thừa số lớn hơn.
Mỗi thừa số được xác nhận là số nguyên tố bằng kiểm tra Miller–Rabin xác định, đã được chứng minh là đúng với các số cỡ này. Số ước được suy ra từ các số mũ: cộng 1 vào mỗi số mũ rồi nhân lại.
Công thức
n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ số ước = (a₁ + 1)(a₂ + 1)…(aₖ + 1)
Ví dụ minh họa
360 = 2 × 2 × 2 × 3 × 3 × 5 = 2³ × 3² × 5. Nó có (3 + 1)(2 + 1)(1 + 1) = 24 ước. Các số nguyên tố gần nhất là 359 và 367.
Câu hỏi thường gặp
1 có phải là số nguyên tố không?
Không. Số nguyên tố có đúng hai ước, là 1 và chính nó; còn 1 chỉ có một ước. Loại trừ nó giữ cho phân tích thừa số nguyên tố là duy nhất.
2 có phải là số nguyên tố chẵn duy nhất không?
Có. Mọi số chẵn khác đều chia hết cho 2, nên có ít nhất ba ước.
Làm thế nào để kiểm tra một số lớn có phải số nguyên tố không?
Chia thử quá chậm với số lớn, nên người ta dùng các kiểm tra như Miller–Rabin. Với bộ cơ số kiểm tra phù hợp, nó cho kết quả chắc chắn với các số cỡ này.