Bài 9.1: Kiểm tra số nguyên tố trong C++

Chào mừng bạn đến với bài viết tiếp theo trong chuỗi blog về C++! Hôm nay, chúng ta sẽ cùng khám phá một chủ đề quen thuộc nhưng đầy thú vị: kiểm tra xem một số có phải là số nguyên tố hay không trong ngôn ngữ C++. Đây là một bài toán kinh điển thường gặp, không chỉ giúp chúng ta rèn luyện kỹ năng lập trình mà còn hiểu sâu hơn về các thuật toán tối ưu.

Vậy, số nguyên tố là gì? Rất đơn giản, một số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước dương phân biệt là 1 và chính nó. Ví dụ: 2, 3, 5, 7, 11... Ngược lại, các số như 1 (chỉ có một ước là 1), 4 (có ước 1, 2, 4), 6 (có ước 1, 2, 3, 6) không phải là số nguyên tố.

Mục tiêu của chúng ta là viết một hàm trong C++ nhận vào một số nguyên dương và trả về true nếu nó là số nguyên tố, false nếu không phải.

Hãy bắt đầu với cách tiếp cận đơn giản nhất nhé!

Phương pháp 1: Kiểm tra từ 2 đến n-1 (Phương pháp cơ bản)

Ý tưởng ban đầu rất trực quan: Để kiểm tra xem một số n có phải là số nguyên tố hay không, chúng ta chỉ cần xem liệu có bất kỳ số nào từ 2 đến n-1 mà n chia hết cho nó hay không. Nếu tìm thấy một số như vậy, thì n chắc chắn không phải là số nguyên tố. Nếu duyệt qua tất cả các số trong phạm vi đó mà không tìm thấy ước nào, thì n là số nguyên tố.

Chúng ta cần lưu ý xử lý các trường hợp đặc biệt:

Các số <= 1 không phải là số nguyên tố.
Số 2 là số nguyên tố duy nhất là số chẵn.

Đây là cách triển khai bằng C++:

#include <iostream> // Can de su dung ham nay, du khong bat buoc trong dinh nghia ham

// Ham kiem tra so nguyen to bang phuong phap co ban
bool laSoNguyenToCoBan(int n) {
    // Buoc 1: Xu ly cac truong hop dac biet
    if (n <= 1) {
        return false; // So <= 1 khong phai so nguyen to
    }

    // Buoc 2: Kiem tra cac uoc tu 2 den n-1
    // Chung ta su dung vong lap for de lap qua cac so i tu 2 den n-1
    for (int i = 2; i < n; ++i) {
        // Phep chia lay du (%): neu n % i == 0, tuc la n chia het cho i
        if (n % i == 0) {
            return false; // Tim thay mot uoc khac 1 va chinh no => khong phai so nguyen to
        }
    }

    // Neu ket thuc vong lap ma khong tim thay uoc nao, thi n la so nguyen to
    return true;
}

Giải thích code:

Hàm laSoNguyenToCoBan nhận vào một số nguyên n và trả về bool (true hoặc false).
Dòng if (n <= 1): Kiểm tra các trường hợp n nhỏ hơn hoặc bằng 1. Các số này theo định nghĩa không phải là số nguyên tố, nên hàm trả về false ngay lập tức.
Vòng lặp for (int i = 2; i < n; ++i): Bắt đầu kiểm tra từ i = 2 (ước nhỏ nhất có thể khác 1) cho đến i = n-1.
Dòng if (n % i == 0): Sử dụng toán tử modulo (%) để kiểm tra xem n có chia hết cho i không. Nếu n % i bằng 0, tức là i là một ước của n và i không phải là 1 (vì i bắt đầu từ 2) và i không phải là n (vì vòng lặp dừng trước n).
Nếu tìm thấy một ước như vậy, hàm trả về false ngay lập tức mà không cần kiểm tra thêm.
Nếu vòng lặp kết thúc (duyệt hết các số từ 2 đến n-1) mà không tìm thấy bất kỳ ước nào, điều đó có nghĩa là n chỉ chia hết cho 1 và chính nó. Hàm trả về true, xác nhận n là số nguyên tố.

Phương pháp này rất dễ hiểu, nhưng bạn có thấy vấn đề gì không? Khi số n trở nên rất lớn, vòng lặp for sẽ phải chạy hàng tỷ lần, điều này làm cho chương trình của chúng ta chạy rất chậm! May mắn thay, chúng ta có thể cải thiện đáng kể hiệu suất.

Phương pháp 2: Kiểm tra đến căn bậc hai của n (Tối ưu 1)

Có một tính chất toán học rất hữu ích ở đây: Nếu một số n có một ước a lớn hơn căn bậc hai của n (a > sqrt(n)), thì n chắc chắn cũng phải có một ước b nhỏ hơn căn bậc hai của n (b < sqrt(n)). Điều này là do n = a * b. Nếu a lớn hơn sqrt(n), thì để tích a * b bằng n, b nhất định phải nhỏ hơn sqrt(n).

Vậy, thay vì kiểm tra tất cả các số từ 2 đến n-1, chúng ta chỉ cần kiểm tra các số từ 2 đến căn bậc hai của n (sqrt(n)). Nếu tìm thấy bất kỳ ước nào trong phạm vi này, n không phải là số nguyên tố. Nếu không tìm thấy, n là số nguyên tố.

Việc này giúp giảm đáng kể số lần lặp của vòng lặp! Ví dụ, để kiểm tra số 100,000,000, phương pháp cơ bản sẽ lặp gần 100 triệu lần, trong khi phương pháp này chỉ lặp khoảng sqrt(100,000,000) = 10,000 lần. Một sự cải thiện khổng lồ!

Hãy xem code C++ cho phương pháp này:

#include <cmath>    // Can de su dung ham sqrt()
#include <iostream> // Can cho cout (trong main vi du)

// Ham kiem tra so nguyen to bang phuong phap toi uu 1 (sqrt)
bool laSoNguyenToSqrt(int n) {
    // Buoc 1: Xu ly cac truong hop dac biet
    if (n <= 1) return false; // So <= 1 khong phai so nguyen to
    if (n == 2) return true;  // So 2 la so nguyen to duy nhat la so chan

    // Buoc 2: Kiem tra cac uoc tu 2 den can bac hai cua n
    // Chung ta co the viet vong lap i*i <= n thay vi i <= sqrt(n)
    // de tranh lam viec voi so thuc va cac van de lam tron tiem an.
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            return false; // Tim thay mot uoc => khong phai so nguyen to
        }
    }

    // Neu ket thuc vong lap ma khong tim thay uoc nao, thi n la so nguyen to
    return true;
}

Giải thích code:

Chúng ta cần #include <cmath> để sử dụng hàm sqrt().
Các trường hợp đặc biệt n <= 1 vẫn được xử lý.
Trường hợp n == 2 được thêm vào để xử lý số 2 một cách nhanh chóng (vì 2 là số nguyên tố và là số chẵn duy nhất).
Vòng lặp for bây giờ chỉ chạy từ i = 2 đến khi i * i vượt quá n. Điều kiện i * i <= n tương đương với i <= sqrt(n), nhưng sử dụng phép nhân số nguyên an toàn hơn.
Bên trong vòng lặp, logic kiểm tra n % i == 0 vẫn giữ nguyên.

Phương pháp này hiệu quả hơn rất nhiều! Nhưng chúng ta có thể làm cho nó còn nhanh hơn nữa không? Chắc chắn rồi!

Phương pháp 3: Tối ưu hơn nữa (Chỉ kiểm tra số lẻ sau số 2)

Hãy suy nghĩ thêm một chút: Sau khi đã kiểm tra và loại bỏ số 2 (số nguyên tố chẵn duy nhất), tất cả các số nguyên tố khác (nếu có) phải là số lẻ. Điều này có nghĩa là chúng ta không cần kiểm tra tính chia hết cho bất kỳ số chẵn nào lớn hơn 2! Nếu một số n (lớn hơn 2) chia hết cho một số chẵn nào đó (ví dụ 4, 6, 8...), thì n chắc chắn cũng phải chia hết cho 2, và chúng ta đã loại trừ trường hợp đó.

Vì vậy, sau khi kiểm tra số 2 và các số chẵn > 2, chúng ta chỉ cần kiểm tra tính chia hết cho các số lẻ bắt đầu từ 3 cho đến căn bậc hai của n. Điều này giảm số lần kiểm tra đi một nửa so với phương pháp trước!

Đây là cách triển khai:

#include <cmath>    // Can de su dung ham sqrt() (neu dung i <= sqrt(n))
#include <iostream> // Can cho cout (trong main vi du)

// Ham kiem tra so nguyen to bang phuong phap toi uu 2 (chi kiem tra so le)
bool laSoNguyenToToiUu(int n) {
    // Buoc 1: Xu ly cac truong hop dac biet va cac so nho
    if (n <= 1) return false; // So <= 1 khong phai nguyen to
    if (n <= 3) return true;  // So 2 va 3 la so nguyen to

    // Buoc 2: Loai tru cac so chan lon hon 2 va cac boi cua 3
    // Chung ta da xu ly so 2 o tren. Bay gio neu n > 3 ma chia het cho 2
    // hoac chia het cho 3 thi khong phai so nguyen to.
    if (n % 2 == 0 || n % 3 == 0) return false;

    // Buoc 3: Kiem tra cac uoc con lai
    // Cac so nguyen to (tru 2 va 3) deu co the viet duoi dang 6k +/- 1.
    // Chung ta chi can kiem tra cac uoc dang i va i+2, bat dau tu i = 5,
    // va tang i len 6 trong moi buoc lap (de kiem tra 5, 7, 11, 13, 17, 19, ...)
    // Chi can kiem tra den can bac hai cua n.
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false; // Tim thay uoc
        }
    }

    // Neu khong tim thay uoc nao sau cac buoc tren, thi n la so nguyen to
    return true;
}

Giải thích code:

Các trường hợp n <= 1, n <= 3 được xử lý nhanh gọn. Số 2 và 3 được xác định là nguyên tố.
Dòng if (n % 2 == 0 || n % 3 == 0): Kiểm tra xem n có chia hết cho 2 hoặc 3 không (đối với n > 3). Nếu có, nó không phải số nguyên tố.
Vòng lặp for bắt đầu từ i = 5.
Điều kiện lặp i * i <= n vẫn giới hạn phạm vi kiểm tra đến căn bậc hai.
Phần i = i + 6: Đây là một thủ thuật tối ưu dựa trên quan sát rằng mọi số nguyên tố lớn hơn 3 đều có dạng 6k - 1 hoặc 6k + 1. Vòng lặp này kiểm tra các ước tiềm năng có dạng i (ban đầu là 5, rồi 11, 17,...) và i + 2 (ban đầu là 7, rồi 13, 19,...). Bằng cách tăng i lên 6 mỗi lần, chúng ta bỏ qua các số chia hết cho 2 hoặc 3 (ví dụ: 6, 9, 10, 12, 15, 16,...).
Dòng if (n % i == 0 || n % (i + 2) == 0): Kiểm tra xem n có chia hết cho i hoặc i+2 không. Nếu có, n không phải số nguyên tố.

Phương pháp này là một trong những cách phổ biến và khá hiệu quả để kiểm tra số nguyên tố cho các giá trị n không quá lớn.

Sử dụng các hàm đã viết

Bây giờ, hãy xem cách chúng ta có thể sử dụng một trong các hàm này trong chương trình C++ hoàn chỉnh, ví dụ dùng hàm tối ưu nhất:

#include <iostream> // Can cho cin/cout
#include <cmath>    // Can cho ham kiem tra toi uu

// Dinh nghia lai ham laSoNguyenToToiUu o day hoac dam bao no da duoc khai bao/dinh nghia
// (Noi dung ham giong nhu da trinh bay o muc "Phuong phap 3")

// Ham kiem tra so nguyen to bang phuong phap toi uu 2 (chi kiem tra so le)
bool laSoNguyenToToiUu(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int num;
    cout << "Moi ban nhap mot so nguyen duong: ";
    cin >> num; // Su dung cin de nhap du lieu

    // Goi ham kiem tra so nguyen to
    if (laSoNguyenToToiUu(num)) {
        // Su dung cout de xuat du lieu
        cout << num << " la so nguyen to." << endl;
    } else {
        cout << num << " khong phai la so nguyen to." << endl;
    }

    return 0; // Ket thuc chuong trinh thanh cong
}

Giải thích code:

Chúng ta #include <iostream> để có thể sử dụng cin để đọc dữ liệu từ bàn phím và cout, endl để in kết quả ra màn hình.
Hàm laSoNguyenToiUu được định nghĩa (hoặc đảm bảo đã được đưa vào từ một file khác).
Trong hàm main, chúng ta khai báo biến num để lưu trữ số người dùng nhập.
Dòng cout << "Moi ban nhap mot so nguyen duong: "; hiển thị lời nhắc cho người dùng.
Dòng cin >> num; đọc số nguyên do người dùng nhập và lưu vào biến num.
Hàm laSoNguyenToiUu(num) được gọi. Kết quả trả về (true hoặc false) sẽ quyết định nhánh if nào được thực thi.
Dựa vào kết quả, chúng ta in ra thông báo phù hợp cho người dùng.

Tổng kết các phương pháp

Bạn thấy đấy, từ một bài toán đơn giản, chúng ta đã đi qua ba phương pháp khác nhau, mỗi phương pháp lại tối ưu hơn phương pháp trước đó về mặt hiệu suất:

Cơ bản: Kiểm tra tất cả các số từ 2 đến n-1. Rất chậm với n lớn.
Tối ưu 1: Kiểm tra tất cả các số từ 2 đến sqrt(n). Nhanh hơn đáng kể.
Tối ưu 2: Kiểm tra số 2 riêng, sau đó chỉ kiểm tra các số lẻ (hoặc theo mẫu 6k +/- 1) từ 3 đến sqrt(n). Nhanh hơn nữa.

Bài tập ví dụ: C++ Bài 4.A6: Đồng hồ kỳ lạ

Một ngày nọ, có một người đàn ông cầm chiếc đồng hồ của anh ấy qua chỗ bạn và nhờ bạn một việc. Chiếc đồng hồ này rất kỳ lạ, nó chỉ có thể hiển thị một số nguyên không âm \(n\) là giây hiện tại của một ngày. Người này chia sẻ rằng chiếc đồng hồ này dùng để đáp ứng thói quen của mình, nhưng giờ anh ấy cần chỉnh lại để đồng hồ hiển thị giờ, phút, giây như mọi đồng hồ bình thường khác để tặng cho người bạn gái của anh ta.

Bạn cảm động trước tình yêu của người đàn ông này dành cho cô gái nên đã nhanh chóng mở máy tính lên và chuẩn bị viết chương trình chuyển đổi giúp người này.

INPUT FORMAT

Một dòng duy nhất chứa một số nguyên dương \(n\ (0\leq n < 86400)\).

OUTPUT FORMAT

In ra trên một dòng theo định dạng hh:mm:ss (hh là hai chữ số của giờ, mm là hai chữ số của phút, ss là hai chữ số của giây).

Ví dụ:

Input

Output

01:00:59

Giải thích ví dụ mẫu:

Ví dụ:

Giải thích: Số giây 3659 tương đương với 1 giờ, 0 phút, và 59 giây, nên định dạng là 01:00:59. <br>

Đây là hướng dẫn giải bài tập chuyển đổi giây sang định dạng giờ:phút:giây (hh:mm:ss) trong C++. Yêu cầu là không cung cấp code hoàn chỉnh mà chỉ đưa ra phương pháp giải và gợi ý sử dụng các công cụ của thư viện chuẩn C++.

Phân tích bài toán:

Bạn được cho một số nguyên không âm n biểu thị tổng số giây đã trôi qua kể từ 00:00:00 của một ngày. Giá trị n nhỏ hơn 86400 (số giây trong một ngày). Nhiệm vụ là chuyển đổi n thành định dạng hh:mm:ss, trong đó hh, mm, ss luôn có hai chữ số (có thêm số 0 ở đầu nếu cần).

Hướng dẫn giải:

Đọc dữ liệu:
- Bạn cần đọc một số nguyên n từ đầu vào chuẩn.
- Sử dụng cin để thực hiện việc này.
Tính toán giờ (hh), phút (mm), giây (ss):
- Tính giờ (hh): Mỗi giờ có 3600 giây (60 phút * 60 giây/phút). Để tìm số giờ đầy đủ trong n giây, bạn cần chia n cho 3600. Sử dụng phép chia lấy phần nguyên (/) để có số giờ.
- Tính số giây còn lại sau khi lấy giờ: Sau khi xác định được số giờ, số giây còn lại chưa đủ một giờ là phần dư khi chia n cho 3600. Sử dụng phép chia lấy dư (%).
- Tính phút (mm): Số giây còn lại (từ bước trước) sẽ được dùng để tính số phút. Mỗi phút có 60 giây. Để tìm số phút đầy đủ trong số giây còn lại, bạn chia số giây còn lại cho 60. Sử dụng phép chia lấy phần nguyên (/).
- Tính giây (ss): Số giây cuối cùng (ss) là số giây còn lại sau khi lấy hết các phút đầy đủ. Đây chính là phần dư khi chia số giây còn lại (từ bước tính phút) cho 60. Sử dụng phép chia lấy dư (%).
Tóm lại, bạn có thể tính toán như sau:
- hh = n / 3600
- mm = (n % 3600) / 60
- ss = n % 60
Định dạng và In kết quả:
- Bạn cần in kết quả theo định dạng hh:mm:ss.
- Quan trọng là hh, mm, ss phải luôn có hai chữ số. Nếu giá trị nhỏ hơn 10, cần thêm số 0 ở phía trước (zero-padding).
- Thư viện chuẩn C++ cung cấp các công cụ để định dạng đầu ra trên cout. Bạn có thể sử dụng các manipulators từ header <iomanip>.
- Cụ thể, setw(2) sẽ thiết lập chiều rộng trường in là 2 ký tự, và setfill('0') sẽ sử dụng ký tự '0' để lấp đầy khoảng trống nếu giá trị không đủ chiều rộng.
- Để in hh với zero-padding, bạn sẽ sử dụng cout << setw(2) << setfill('0') << hh;.
- Sau đó, in ký tự : giữa các phần.
- Lặp lại quy trình định dạng cho mm và ss.
- Cuối cùng, nhớ xuống dòng sau khi in xong.

Các bước thực hiện trong code:

Include các header cần thiết (iostream cho nhập/xuất, iomanip cho định dạng).
Đọc giá trị n từ cin.
Thực hiện các phép tính để tìm hh, mm, ss.
In hh với định dạng hai chữ số có zero-padding.
In ký tự :.
In mm với định dạng hai chữ số có zero-padding.
In ký tự :.
In ss với định dạng hai chữ số có zero-padding.
In ký tự xuống dòng (endl).