Kiểm tra số tự nhiên có phải là số nguyên tố hay không

Người viết: NHÓM CHUYÊN GIA lúc 08.06.2026
TRUNG HỌC CƠ SỞ

Sử dụng máy tính cầm tay, hãy kiểm tra các số tự nhiên sau có phải là số nguyên tố hay không.

997
1009
100003
2147483647

Giải

Xác định 997 có phải là số nguyên tố hay không.

Sử dụng chức năng phân tích thừa số thành số nguyên tố (FACT) của máy tính.

Vậy 997 là số nguyên tố.

Xác định 1009 có phải là số nguyên tố hay không.

Sử dụng chức năng phân tích thừa số thành số nguyên tố (FACT) của máy tính.

Vì chức năng phân tích thành thừa số nguyên tố chỉ lưu trữ các số nguyên tố dưới 4 chữ số (từ 2 đến 997) nên chúng ta cần sử dụng phương pháp khác để kiểm tra số 1009.

Sử dụng chức năng bảng giá trị của máy tính, đặt hàm f(x) như sau

Cho giá trị x chạy từ 3 đến căn bậc hai của 1009, bước nhảy bằng 2.

Xem kết quả trên bảng giá trị, nếu xuất hiện giá trị nguyên thì kết luận 1009 là hợp số, nếu không xuất hiện giá trị nguyên thì kết luận 1009 là số nguyên tố.

Vậy 1009 là số nguyên tố.

Xác định 100003 có phải là số nguyên tố hay không.

Số 100003 có căn bậc 2 là 316,2325 nên việc lập và kiểm tra các ước trên bảng giá trị sẽ không hiệu quả (có quá nhiều dòng phải kiểm tra).

Chúng ta sẽ sử dụng một mẹo sau để kiểm tra số 100003 có phải là số nguyên tố hay không trên máy tính bằng cách xét tổng sau

Với A = 100003, ta rà soát tất cả các hiệu ở mẫu số. Nếu tất cả các hiệu đều khác 0 (A không chia hết) thì tổng đạt được sẽ là 0. Nếu có một hiệu bằng 0 (A chia hết cho 2x + 1) thì phân số sẽ không tính được, máy tính dừng tính toán và xuất ra kết quả Math Error.

Vậy 100003 là số nguyên tố.

Xác định 2147483647 có phải là số nguyên tố hay không.

Số 2147483647 có căn bậc 2 là 46340,95 nên việc lập tổng chia cho các số lẻ như trên sẽ không hiệu quả vì số lượng phần tử cần tính toán quá lớn.

Nhận xét rằng 2147483647 = 2³¹ - 1 nên đây là số Marsenne M(31).

Ta có thể sử dụng định lí Euler cho số Marsenne để kiểm tra ước số của M(31) như sau:

Vì 31 là số nguyên tố nên ước nguyên tố của M(31) nếu có phải có dạng q = 2 . 31 . k + 1 = 62k + 1.
Thực hiện phép cộng tương tự ví dụ trên, với các x nhận giá trị là 62k + 1.