Kiểm tra xem một số n có phải là số nguyên tố hay không vốn là một bài toán đơn giản chúng ta đều tiếp xúc từ khi mới bập bẹ những bài toán lập trình đầu tiên. Vậy làm sao để kiểm tra chúng một cách dễ dàng nhất, hãy cùng Cao đẳng FPT Mạng cá cược bóng đá tìm hiểu về thao tác này.  

Số nguyên tố?

Số nguyên tố được định nghĩa như sau: Số nguyên tố là một số nguyên dương chỉ có 2 ước là 1 và chính nó. Về cơ bản, cái tên số nguyên tố xuất phát từ chính vai trò của nó: “Dùng để xây dựng nên các số khác”. Số nguyên tố không thể chia nhỏ thành các phần bằng nhau khác 1 được, nó đơn giản được dung tạo nên những thứ khác, là nguyên tố cho chính các con số. Số nguyên tố trải dài trên trục số. Do đó sẽ có những số từ nhỏ đến siêu lớn.

Kiểm tra số nguyên tố

Bài toàn đặt ra cho chúng ta đó là làm sao kiểm tra được một số có phải nguyên tố hay không. Điều này đặt ra cho chúng ta những vấn đề hết sức thú vị. Chúng ta không thể đoán mò xem một số có là số nguyên tố hay không. Cũng không có bất kì công thức nào để tính ra được một số nguyên tố vì căn bản những số này rất lạ, hoàn toàn mang các tính chất riêng.

Vậy làm sao để kiểm tra chúng?

Hãy bắt đầu bằng cách lật lại định nghĩa. Khi bế tắc trong mọi vấn đề, chúng ta hay thử lật lại mọi thứ một lần trước khi bỏ cuộc.

Số nguyên tố là gì nhỉ? Số nguyên dương chỉ có 2 ước duy nhất là 1 và chính nó. Dữ liệu đầu tiên chính là có 2 ước là 1 và chính nó. Như vậy chúng ta chỉ cần kiểm tra xem số đó có chia hết cho 1 hay chính nó! Điều này là luôn đúng? 1 điều luôn đúng lại có thể là định nghĩa ư? Hãy chú ý lại 1 từ “Chỉ có”. Hãy cùng nhau phân tích từ đó nào. Thế nào là chỉ có? Chỉ có là 1 tính từ khẳng định về khả năng sở hữu hữu hạn.

Việc một số chỉ có 2 ước là 1 và chính nó đòng nghĩa với việc số đó chỉ có khả năng chia hết cho 1 và chính nó. Điều khẳng định luôn đúng này đồng thời tương đương với việc phủ định khả năng nó có thể chia hết cho bất cứ số nào khác. Mà một số không thể chia hết cho bất kì số nào khác lớn hơn nó ngoại trừ số 0, đó đó nếu tính từ số 2 đến n-1 thì nếu n không phải số nguyên tố thì chắc chắn n sẽ chia hết cho một số nào đó. Như vậy cách để chúng ta kiểm tra cũng khá đơn giản: Sử dụng vòng lặp và kiểm tra tính chia hết, nếu số đó không chia hết cho bất kì số nào lớn hơn 1 và nhỏ hơn nó thì đó là một số nguyên tố.

Một vài điều hay ho
Thuật toán kiểm tra đã có, ta sẽ làm như sau giả sử rằng n là số cần kiểm tra:

int count = 0; for(int i = 2; i < n ; i++){ if(n % i == 0) count++; } if(count > 0) => n không phải số nguyên tố else => n là số nguyên tố.

Đó là cách cơ bản nhất để kiểm tra. Vậy còn cách nào khác dễ hơn, hay chí ít ngắn gọn hơn không?
Đầu tiên hãy thử xem tính chất của 1 số nguyên tố. Trừ 2 là số nguyên tố chẵn duy nhất thì mọi số nguyên tố khác đều lẻ. Do đó thay vì kiểm tra tất cả các số từ 2 đến n-1 ta chỉ cần kiểm tra các số lẻ trong đoạn đó, số lượng công việc cần làm cơ bản đã giảm đi 1 nửa.

Bây giờ hãy thử hình dung nếu ta kiểm tra một số nguyên tố có độ lớn khoảng 1000000 (dĩ nhiên 1000000 là không phải nhưng hãy ước lượng như vậy nhé). Nếu áp dụng cách vừa rồi thì chúng ta cần đến 500000 phép thử. Nếu mỗi phép tính đó tốn 0.000001 giây thì cũng mất tới 0.5 giây. Hình như có vẻ vẫn hơi lâu thì phải.

Xét về mặt toán học, khi một số a bất kì chia hết cho một số lớn hơn hoặc bằng căn bậc 2 của nó thì kết quả thu được khi chia luôn nhỏ hơn hoặc bằng giá trị căn bậc 2. Do đó khi thực hiện việc kiểm tra, ta chỉ cần kiểm tra những số không quá căn bậc hai của a. Hình dung xem căn bậc hai của 1000000 chỉ là 1000, kết hợp thêm với cách sử dụng số lẻ chúng ta chỉ cần vẻn vẹn 500 phép thử tương đương với 0.0005 giây. Đủ nhanh chưa nhỉ?

Bên cạnh đó có rất nhiều các phương pháp để chúng ta xử lý. Bài toán về số nguyên tố cũng chỉ là một trong số rất nhiều ví dụ vui về cách mà chúng ta nhìn nhận vấn đề. Không chỉ rèn luyện về khả năng code mà tư duy mở rộng cũng là một yếu tố rất hay ho. Bởi vậy đừng gò bó bản thân với những suy nghĩ theo lối mòn, biết đâu đó với những suy nghĩ mở rông, chúng ta sẽ có kết quả tích cực hơn rất nhiều.

Bộ môn Ứng dụng phần mềm

Cao đẳng FPT Mạng cá cược bóng đá Hà Nội