Giải phương trình bậc nhất ax + b = 0 trong C / C++ 
Lệnh Alert trong Javascript Thuật toán kiểm tra số nguyên tố trong C / C++
Trong bài viết này, codehow sẽ giới thiệu đến các bạn thuật toán kiểm tra số nguyên tố trong C / C++. Khi bắt đầu học ngôn ngữ lập trình thì các bạn cần phải biết đến khái niệm thuật toán, vì đây là giải thuật giúp các bạn lập trình nhanh hơn.
Trước khi đi vào tìm hiểu cách viết thuật toán, các bạn cùng mình tìm hiểu qua khái niệm số nguyên tố là gì đã nhé.
Số nguyên tố là gì?
Ví dụ: Các số nguyên tố {2, 3, 5, 7, 11, ...}
Trong các số nguyên tố thì số 2 là số chẵn duy nhất. Và số nguyên tố là một dãy vô hạn, nghĩa là không có số nguyên tố lớn nhất.
Ví dụ ta có số 5 là số nguyên tố, bởi vì trong khoản từ 2 đến 7 nó chỉ chia hết cho chính nó mà thôi.
Thuật toán kiểm tra số nguyên tố trong C / C++
Qua phần một thì các bạn cũng đã hiểu sơ qua về số nguyên tố là gì và một số tính chất đặc biệt của nó rồi đúng không ạ.
Vậy bây giờ, chúng ta cùng tìm hiểu về thuật toán kiểm tra số nguyên tố trong C / C++ thôi nào.
Cách 1: Lặp từng phần tử với bước nhảy 1
Dưới đây là thuật toán kiểm tra số n có phải là số nguyên tố hay không, nếu phải thì return true và ngược lại thì return false.
bool laSoNguyenTo1(int n)
{
if (n < 2){
return false;
}
for (int i = 2; i < (n - 1); i++){
if (n % i == 0){
return false;
}
}
return true;
}Giải thích thuật toán:
- Kiểm tra điều kiện nếu n < 2 thì return false vì đây không phải là số nguyên tố.
- Sử dụng vòng lặp for với bước nhảy 1, lặp từ 2 đến n - 1. Nếu tồn tại một số nào mà n chia hết thì return false, ngược lại thì return true.
Cách 2: Lặp từng phần tử với bước nhảy 2
Như đã nói ở phần một, trong các số nguyên tố thì số 2 là số chẵn duy nhất. Vì vậy ta có thể loại bỏ số 2 ra khỏi vòng lặp và bắt đầu lặp các số lẻ từ 3 mà thôi. Cách này sẽ tối ưu hơn rất nhiều so với cách một vì nó chỉ lặp bằng một nữa so với cách một.
bool laSoNguyenTo2(int n)
{
if (n < 2){
return false;
}
if (n == 2){
return true;
}
if (n % 2 == 0){
return false;
}
for (int i = 3; i < (n - 1); i += 2){
if (n % i == 0){
return false;
}
}
return true;
}Giải thích thuật toán:
- Kiểm tra nếu n < 2 thì đây không phải là số nguyên tố.
- Nếu n = 2 thì đây là số nguyên tố.
- Nếu n % 2 == 0 (là số chẵn) thì không phải là số nguyên tố.
- Sử dụng vòng lặp for với bước nhảy 2, bắt đầu từ 3 đến n - 1. Nếu tồn tại số nào mà n chia hết thì đó không phải là số nguyên tố, ngược lại là số nguyên tố.
*Lưu ý: Để tối ưu hơn nữa ta có thể sử dụng điều kiện dừng của vòng lặp là n / 2 thay vì n - 1, vì một số sẽ không bai giờ chia hết cho số lớn hơn một nữa của nó.
Ví dụ thuật toán kiểm tra số nguyên tố trong C / C++
Trong phần này mình sẽ thực hiện ví dụ sử dụng thuật toán kiểm tra số nguyên tố trong C / C++. Mình sẽ sử dụng hai thuật toán ở phần trên để làm ví dụ, các bạn có thể tham khảo nhé !!!
Ví dụ 1: Sử dụng thuật toán kiểm tra số nguyên tố trong C / C++ với bước nhảy một để kiểm tra số người dùng nhập có phải là số nguyên tố hay không.
Chương trình C:
#include <stdio.h>
#include <stdbool.h>
bool laSoNguyenTo1(int n)
{
if (n < 2){
return false;
}
for (int i = 2; i < (n - 1); i++){
if (n % i == 0){
return false;
}
}
return true;
}
int main(void) {
int n;
printf("Nhập vào số cần kiểm tra: ");
scanf("%d", &n);
if (laSoNguyenTo1(n)){
printf("%d là số nguyên tố.",n);
}
else {
printf("%d không phải là số nguyên tố.",n);
}
printf("\n----------------------------------\n");
printf("Chương trình này được đăng tại codehow.net");
return 0;
}Kết quả:
Chương trình C++:
#include <iostream>
using namespace std;
bool laSoNguyenTo1(int n)
{
if (n < 2){
return false;
}
for (int i = 2; i < (n - 1); i++){
if (n % i == 0){
return false;
}
}
return true;
}
int main() {
int n;
cout << "Nhập vào số cần kiểm tra: ";
cin >> n;
if (laSoNguyenTo1(n)){
cout <<n<< " là số nguyên tố.";
}
else {
cout <<n<< " không phải là số nguyên tố";
}
cout<<"\n----------------------------------\n";
cout<<"Chương trình này được đăng tại codehow.net";
return 0;
}Kết quả:
Ví dụ 2: Sử dụng thuật toán kiểm tra số nguyên tố trong C / C++ với bước nhảy hai để kiểm tra số người dùng nhập có phải là số nguyên tố hay không.
Chương trình C:
#include <stdio.h>
#include <stdbool.h>
bool laSoNguyenTo2(int n)
{
if (n < 2){
return false;
}
if (n == 2){
return true;
}
if (n % 2 == 0){
return false;
}
for (int i = 3; i < (n - 1); i += 2){
if (n % i == 0){
return false;
}
}
return true;
}
int main(void) {
int n;
printf("Nhập vào số cần kiểm tra: ");
scanf("%d", &n);
if (laSoNguyenTo2(n)){
printf("%d là số nguyên tố.",n);
}
else {
printf("%d không phải là số nguyên tố.",n);
}
printf("\n----------------------------------\n");
printf("Chương trình này được đăng tại codehow.net");
return 0;
}Kết quả:
Chương trình C++:
#include <iostream>
using namespace std;
bool laSoNguyenTo2(int n)
{
if (n < 2){
return false;
}
if (n == 2){
return true;
}
if (n % 2 == 0){
return false;
}
for (int i = 3; i < (n - 1); i += 2){
if (n % i == 0){
return false;
}
}
return true;
}
int main() {
int n;
cout << "Nhập vào số cần kiểm tra: ";
cin >> n;
if (laSoNguyenTo2(n)){
cout <<n<< " là số nguyên tố.";
}
else {
cout <<n<< " không phải là số nguyên tố";
}
cout<<"\n----------------------------------\n";
cout<<"Chương trình này được đăng tại codehow.net";
return 0;
}Kết quả:
Như vậy là chúng ta đã cùng nhau tìm hiểu về giải thuật kiểm tra số nguyên tố trong C / C++. Các bạn hãy luyện tập thật nhiều để có thể sử dụng nó một cách thông thạo nhé, chúc các bạn thành công !!!
