Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thuật toán kiếm tra số nguyên tố
Trong bài này mình sẽ trình bày thuật toán để kiểm tra một số có phải là số nguyên tố hay không, sau khi giới thiệu xong thuật toán mình sẽ sử dụng ngôn ngữ C++ để giải mẫu cho các bạn. Trước tiên chúng ta tìm hiểu định nghĩa số nguyên tố là gì đã nhé.
1. Số nguyên tố là gì?
Theo định nghĩa của Wikipedia thì số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. Theo định nghĩa này thì các số 2, 3, 5, 7, 11, ... là các số nguyên tố, trong đó số 2 là số nguyên tố chẵn duy nhất. Cũng như tính chất của số nguyên dương, chúng ta chỉ tìm thấy số nguyên tố nhỏ nhất chứ không thể tìm thấy số nguyên tố lớn nhất.
Ví dụ: 7 là số nguyên tố vì trong khoảng từ 2 - 6 không tồn tại số nào mà 7 chia hết cả.
2. Thuật toán kiểm tra số nguyên tố
Dựa vào định nghĩa của số nguyên tố chúng ta sẽ có một số cách giải như sau (các ví dụ được viết bằng ngôn ngữ C++):
Bài viết này được đăng tại [free tuts .net]
Cách 1: Lặp từng phần tử với bước nhảy 1
Giả sử cần kiểm tra số n có phải là số nguyên tố hay không thì các bước thực hiện như sau:
- Bước 1: Nhập vào
n - Bước 2: Kiểm tra nếu
n < 2thì kết luậnnkhông phải là số nguyên tố - Bước 3: Lặp từ
2tới(n-1), nếu trong khoảng này tồn tại số mànchia hết thì kết luậnnkhông phải là số nguyên tố, ngược lạinlà số nguyên tố.
bool laSoNguyenTo1(int n)
{
// Neu n < 2 thi khong phai la SNT
if (n < 2){
return false;
}
for (int i = 2; i < (n - 1); i++){
if (n % i == 0){
return false;
}
}
return true;
}
Hàm main:
void main()
{
int n;
cout << "Nhap so can kiem tra";
cin >> n;
if (laSoNguyenTo1(n)){
cout << "La so nguyen to";
}
else {
cout << "Khong phai so nguyen to";
}
}
Cách 2: Lặp từng phần tử với bước nhảy 2
Theo định nghĩa thì số 2 là số nguyên tố chẵn duy nhất, vì vậy ta sẽ loại 2 ra khỏi vòng lặp và trong thân vòng lặp chỉ kiểm tra các số lẻ mà thôi, cách này sẽ tối ưu hơn cách 1 rất nhiều.
bool laSoNguyenTo2(int n)
{
// Neu n < 2 thi khong phai la SNT
if (n < 2){
return false;
}
// Neu n = 2 la SNT
if (n == 2){
return true;
}
// Neu n la so chan thi ko phai la SNT
if (n % 2 == 0){
return false;
}
// Lap qua cac so le
for (int i = 3; i < (n - 1); i += 2){
if (n % i == 0){
return false;
}
}
return true;
}
Hàm main:
void main()
{
int n;
cout << "Nhap so can kiem tra";
cin >> n;
if (laSoNguyenTo2(n)){
cout << "La so nguyen to";
}
else {
cout << "Khong phai so nguyen to";
}
}
3. Lời kết
Vẫn còn rất nhiều cách khác nhưng chung quy lại vẫn phải bám vào định nghĩa số nguyên tố là gì. Ví dụ trong vòng lặp điểm dừng sẽ là (n/2) thay vì (n-1) vì theo lý thuyết thì một số không bao giờ chia hết cho số một nửa của nó. Ví dụ số 9 thì số một nửa của nó là số (9 : 2 = 4), như vậy ta chỉ cần kiểm tra các số từ 2,3,4 mà thôi, còn các số 5,6,7,8 chắc chẵn 9 sẽ không chia hết.
for (int i = 3; i <= (n/2); i += 2){
if (n % i == 0){
return false;
}
}
