Phân tích một số rất lớn ra thừa số nguyên tố.

Phân tích số 8788763 ra thừa số nguyên tố.

Ta có:

Ta kiểm tra số 8788763 là hợp số theo quy tắc

(nếu kết quả là -1 thì nó là hợp số,

còn nếu kết quả bằng 0 hoặc bằng 1 thì ta phải kiểm tra xem nó là số nguyên tố/hay không là số nguyên tố theo các phương pháp đã biết).

Để phân tích số 8788763 ra thừa số nguyên tố ta sử dụng thuật toán Pollard's Rho.

THUẬT TOÁN POLLARD'S RHO

Gán số đã cho vào biến nhớ M. Thuật toán này dựa vào hàm số
Xây dựng hai dãy số (a_n) và (b_n) như sau:
Sau mỗi bước n, tính GCD(|a_n-b_n|,M). Đến một bước nào đó mà GCD(|a_n-b_n|,M) lớn hơn 1 và nhỏ hơn M thì

GCD(|a_n-b_n|,M) đó là thừa số nguyên tố thứ nhất.

THAO TÁC TRÊN MÁY TÍNH

và

Gán số 8788763 vào biến nhớ M .
Nhập lên màn hình trên một dòng:
Bấm CALC, nhập A=2, bảo lưu M (nghĩa là bấm mũi tên xuống) và nhập B=2, sau đó nhấn phím 4 lần, các lần sau bấm nhanh phím 5 lần, Nếu thấy kết quả là 1 thì tiếp tục cho đến khi thấy GCD lớn hơn 1 thì đó chính là thừa số nguyên tố thứ nhất, cụ thể trong bài toán này máy tính xuất ra kết quả 1659. Muốn tìm thừa số nguyên tố thứ hai ta lấy M chia cho thừa số nguyên tố thứ nhất. Kiểm tra xem thừa số thứ hai có là số nguyên tố không.
Thừa số thứ hai là 5179. Ta kiểm tra được thừa số thứ hai này là số nguyên tố. Vậy
8788763=1697 x 5179.

Khôi phục mật khẩu

TỔNG TIỀN:	0₫
Xem giỏ hàng	Thanh toán