BITEXEDU Chuyên trang chia sẻ tài liệu, kinh nghiệm ứng dụng giải toán trên máy tính cầm tay
Thuật toán chia thử (trial divison) phân tích một số ra thừa số nguyên tố
- 05/01/2026
- 1,052 lượt xem
Đặt vấn đề. Khi ta gặp một số rất lớn (chẳng hạn $8788763$) rất khó để phân tích ra thừa số nguyên tố  . Máy tính cầm tay là một trong công cụ thực hiện việc phân tích này, thông qua chức năng lập bảng giá trị cho hai hàm số. |
| Ta chọn số nguyên lẻ lớn nhất nhỏ hơn hay bằng $\sqrt{n}=\sqrt{8788763}$ là số $2963$. Ta lần lượt chia $8788763$ cho các số nguyên lẻ bắt đầu từ $2963$ tất nhiên đến số $3$. Nếu có một kết quả là số nguyên thì ta dừng lại để phân tích $n$ thành tích của hai số, rất có khả năng là hai số nguyên tố. Rất may là hai số này gần nhau nên chỉ cần thực hiện vài bước. |
Ta mở chức năng Bảng giá trị, nhập hai hàm số $f(x)=\dfrac{8788763}{x}\ ; \ g(x)=\dfrac{8788763}{x-60}$ (để liệt kê 120 phép chia lên một trang màn hình).
Trang đầu tiên: $\text{Start}\ = 2963$, $\text{End}\ = \text{Start} -58\ ; \ \text{Step}\ = -2 $ (hiển thị 120 phép chia đầu tiên, nếu có kết quả nguyên thì dừng).
Trang 1: $\text{Start}\ = 2963 -1\times 118$, $\text{End}\ = \text{Start} -58\ ; \ \text{Step}\ = -2 $ (hiển thị 120 phép chia đầu tiên, nếu có kết quả nguyên thì dừng).
Trang 2: $\text{Start}\ = 2963-2 \times 118$, $\text{End}\ = \text{Start} -58\ ; \ \text{Step}\ = -2 $ (hiển thị 120 phép chia tiếp theo, nếu có kết quả nguyên thì dừng).
Trang thứ $k$: $\text{Start}\ = 2963-k\times 118$, $\text{End}\ = \text{Start} -58\ ; \ \text{Step}\ = -2 $ (hiển thị tiếp 120 phép chia tiếp theo, ta thấy có kết quả nguyên ). Tại đây ta có sự phân tích ra thừa số nguyên tố.
Chúng tôi kiên trì thực hiện 11 trang màn hình (nghĩa là thử với hơn $1320$ số lẻ) để từ $2963$ giảm xuống $1697$.
.
Vậy $8788763=5179\times 1697$.
About TS. Nguyễn Thái Sơn
