Khóa học CTDL và GT

Bài 3.3: Thuật toán Euclid và ƯCLN, BCNN,

Chào mừng bạn trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật của chúng ta! Hôm nay, chúng ta sẽ lặn sâu vào một chủ đề nghe có vẻ đơn giản trong toán học, nhưng lại cực kỳ mạnh mẽ và hiệu quả trong lập trình và các bài toán thực tế: Ước số chung lớn nhất (ƯCLN) và Bội số chung nhỏ nhất (BCNN), cùng với "ngôi sao" của bài viết này – Thuật toán Euclid.

Tại sao chúng ta cần học về ƯCLN và BCNN trong môn CTDL&GT? Bởi vì chúng xuất hiện trong nhiều bài toán, từ những vấn đề lý thuyết số cơ bản đến các ứng dụng phức tạp hơn trong mật mã, đồ họa máy tính, và thậm chí là tối ưu hóa tài nguyên. Và Thuật toán Euclid chính là phương pháp ưu việt để tìm ƯCLN, từ đó dễ dàng suy ra BCNN.

Hãy bắt đầu hành trình khám phá nhé!

1. Ước số chung lớn nhất (ƯCLN) - GCD

Ước số chung lớn nhất (ƯCLN) của hai hoặc nhiều số nguyên dương là số nguyên dương lớn nhất mà là ước của tất cả các số đó. Trong tiếng Anh, nó được gọi là Greatest Common Divisor (GCD).

Ví dụ:

• Ước của 12 là: 1, 2, 3, 4, 6, 12
• Ước của 18 là: 1, 2, 3, 6, 9, 18
• Các ước chung của 12 và 18 là: 1, 2, 3, 6
• Ước số chung lớn nhất của 12 và 18 là: 6. Ký hiệu: ƯCLN(12, 18) = 6 hoặc gcd(12, 18) = 6.

Phương pháp "Ngây thơ" (Naive Method)

Cách đơn giản nhất để tìm ƯCLN của hai số nguyên dương a và b là duyệt qua tất cả các số từ min(a, b) xuống đến 1. Số đầu tiên mà chia hết cho cả a và b chính là ƯCLN.

Ví dụ tìm ƯCLN(12, 18):

• min(12, 18) = 12.
• Kiểm tra 12: 12 không chia hết 18.
• Kiểm tra 11: 11 không chia hết 12.
• ...
• Kiểm tra 6: 12 chia hết 6 (12 = 6 2), 18 chia hết 6 (18 = 6 3). Cả hai đều chia hết! Vậy ƯCLN(12, 18) = 6.

Phương pháp này hoạt động, nhưng nó không hiệu quả lắm khi a và b là những số rất lớn. Thời gian thực hiện sẽ tỉ lệ với giá trị nhỏ hơn trong hai số đó. Chúng ta cần một cái gì đó nhanh hơn, thông minh hơn.

Đó là lúc Thuật toán Euclid bước vào sàn diễn!

2. Thuật toán Euclid - Vẻ đẹp của phép chia lấy dư

Thuật toán Euclid là một trong những thuật toán cổ xưa nhất còn được sử dụng rộng rãi cho đến ngày nay. Nó dựa trên một nguyên lý toán học tuyệt vời và đơn giản:

Nguyên lý: Ước số chung lớn nhất của hai số nguyên a và b (với a > b và b ≠ 0) cũng chính là ước số chung lớn nhất của số b và phần dư của phép chia a cho b (a % b). Nói cách khác: gcd(a, b) = gcd(b, a % b)

Trường hợp cơ bản (Base Case): Khi một trong hai số bằng 0, ƯCLN của số còn lại và 0 chính là giá trị tuyệt đối của số đó. gcd(a, 0) = |a|. Thông thường, chúng ta chỉ xét với số dương, nên gcd(a, 0) = a.

Tại sao gcd(a, b) = gcd(b, a % b) lại đúng?

Giả sử d là một ước chung của a và b. Điều này có nghĩa là a = d * k1 và b = d * k2 với k1, k2 là các số nguyên. Ta biết rằng a % b có thể được viết dưới dạng a = q * b + (a % b), trong đó q là thương của phép chia a cho b. Thay thế a và b bằng dạng d * k: d * k1 = q * (d * k2) + (a % b) d * k1 = d * q * k2 + (a % b) d * k1 - d * q * k2 = a % b d * (k1 - q * k2) = a % b

Điều này cho thấy rằng d cũng là ước của a % b. Như vậy, bất kỳ ước chung nào của a và b cũng là ước chung của b và a % b.

Ngược lại, giả sử d' là một ước chung của b và a % b. Điều này có nghĩa là b = d' * m1 và a % b = d' * m2 với m1, m2 là các số nguyên. Từ phương trình a = q * b + (a % b), ta thay thế b và a % b: a = q * (d' * m1) + (d' * m2) a = d' * (q * m1) + d' * m2 a = d' * (q * m1 + m2)

Điều này cho thấy rằng d' cũng là ước của a. Như vậy, bất kỳ ước chung nào của b và a % b cũng là ước chung của a và b.

Vì tập hợp các ước chung của {a, b} và tập hợp các ước chung của {b, a % b} là giống hệt nhau, nên ước chung lớn nhất của chúng cũng phải giống nhau. Thật thanh lịch phải không nào?

Triển khai Thuật toán Euclid bằng C++

Chúng ta có thể triển khai thuật toán này theo hai cách chính: đệ quy và lặp.

2.2.1. Triển khai Đệ quy (Recursive Implementation)

Phiên bản đệ quy theo sát định nghĩa: gcd(a, b) gọi đệ quy gcd(b, a % b) cho đến khi số thứ hai bằng 0.

#include <iostream>

// Hàm tính ƯCLN sử dụng thuật toán Euclid (Đệ quy)
int gcd_recursive(int a, int b) {
    // Case base: Nếu b bằng 0, ƯCLN là a
    if (b == 0) {
        return a;
    }
    // Bước đệ quy: gcd(a, b) = gcd(b, a % b)
    return gcd_recursive(b, a % b);
}

Giải thích code:

• Hàm gcd_recursive nhận hai số nguyên a và b.
• Dòng if (b == 0) kiểm tra điều kiện dừng của đệ quy. Khi b đạt đến 0, chúng ta trả về a (số còn lại), đây là ƯCLN.
• Dòng return gcd_recursive(b, a % b); chính là trái tim của thuật toán. Chúng ta gọi lại hàm gcd_recursive với tham số thứ nhất là số b cũ, và tham số thứ hai là phần dư của a chia cho b. Quá trình này lặp lại cho đến khi phần dư bằng 0.

2.2.2. Triển khai Lặp (Iterative Implementation)

Phiên bản lặp sử dụng một vòng lặp để thực hiện các bước tương tự như đệ quy, nhưng không sử dụng ngăn xếp (stack) của hàm đệ quy. Điều này đôi khi hiệu quả hơn và tránh được lỗi tràn ngăn xếp (stack overflow) với các số quá lớn.

#include <iostream>

// Hàm tính ƯCLN sử dụng thuật toán Euclid (Lặp)
int gcd_iterative(int a, int b) {
    // Sử dụng vòng lặp while cho đến khi b bằng 0
    while (b != 0) {
        // Lưu lại giá trị hiện tại của b vào biến tạm
        int temp = b;
        // Cập nhật b thành phần dư của a chia cho b
        b = a % b;
        // Cập nhật a thành giá trị cũ của b (đã lưu trong temp)
        a = temp;
    }
    // Khi b bằng 0, giá trị của a chính là ƯCLN
    return a;
}

Giải thích code:

• Hàm gcd_iterative nhận hai số nguyên a và b.
• Vòng lặp while (b != 0) sẽ tiếp tục chạy cho đến khi b bằng 0.
• Bên trong vòng lặp:
  • int temp = b;: Chúng ta cần lưu giá trị hiện tại của b vì chúng ta sẽ gán giá trị mới cho b ở bước tiếp theo.
  • b = a % b;: Giá trị b mới là phần dư của a chia cho b.
  • a = temp;: Giá trị a mới là giá trị b cũ (đã lưu trong temp).
• Quá trình này lặp lại, liên tục giảm giá trị của b (thông qua phép lấy phần dư) cho đến khi nó bằng 0. Khi đó, vòng lặp dừng lại, và giá trị cuối cùng của a chính là ƯCLN.

Cả hai phiên bản đệ quy và lặp đều cho kết quả chính xác và có độ phức tạp thời gian là O(log(min(a, b))), nhanh hơn rất nhiều so với phương pháp "ngây thơ" có độ phức tạp O(min(a, b)). Đây là một ví dụ tuyệt vời về cách một thuật toán thông minh có thể tạo ra sự khác biệt lớn về hiệu suất.

Ví dụ minh họa C++ cho ƯCLN

Hãy sử dụng các hàm vừa viết để tính ƯCLN của vài cặp số.

#include <iostream> // Cần cho std::cout, std::endl
#include <cmath>    // Cần cho std::abs nếu xử lý số âm

// Bao gồm các hàm gcd_recursive và gcd_iterative đã viết ở trên
// Giả sử bạn đã định nghĩa chúng trong cùng file hoặc include từ file khác

int gcd_recursive(int a, int b) {
    // Để đơn giản, xử lý số âm bằng cách lấy giá trị tuyệt đối
    a = std::abs(a);
    b = std::abs(b);
    if (b == 0) {
        return a;
    }
    return gcd_recursive(b, a % b);
}

int gcd_iterative(int a, int b) {
     // Để đơn giản, xử lý số âm bằng cách lấy giá trị tuyệt đối
    a = std::abs(a);
    b = std::abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}


int main() {
    int num1 = 48;
    int num2 = 18;

    std::cout << "--- Minh hoa tinh Toan UCLN ---" << std::endl;

    // Su dung phien ban de quy
    int result_recursive = gcd_recursive(num1, num2);
    std::cout << "UCLN(" << num1 << ", " << num2 << ") (De quy) = " << result_recursive << std::endl; // Ket qua: 6

    // Su dung phien ban lap
    int result_iterative = gcd_iterative(num1, num2);
    std::cout << "UCLN(" << num1 << ", " << num2 << ") (Lap) = " << result_iterative << std::endl; // Ket qua: 6

    std::cout << std::endl; // Xuong dong

    // Thu voi cap so khac
    num1 = 101; // So nguyen to
    num2 = 103; // So nguyen to
    result_recursive = gcd_recursive(num1, num2);
    result_iterative = gcd_iterative(num1, num2);
    std::cout << "UCLN(" << num1 << ", " << num2 << ") (De quy) = " << result_recursive << std::endl; // Ket qua: 1
    std::cout << "UCLN(" << num1 << ", " << num2 << ") (Lap) = " << result_iterative << std::endl; // Ket qua: 1

     std::cout << std::endl; // Xuong dong

    // Thu voi so lon hon va so nho hon nhieu
    num1 = 1000;
    num2 = 25;
    result_recursive = gcd_recursive(num1, num2);
    result_iterative = gcd_iterative(num1, num2);
    std::cout << "UCLN(" << num1 << ", " << num2 << ") (De quy) = " << result_recursive << std::endl; // Ket qua: 25
    std::cout << "UCLN(" << num1 << ", " << num2 << ") (Lap) = " << result_iterative << std::endl; // Ket qua: 25

    std::cout << std::endl; // Xuong dong

     // Thu voi so am (Can them std::abs() trong ham tinh UCLN)
    num1 = -48;
    num2 = 18;
     result_recursive = gcd_recursive(num1, num2);
    result_iterative = gcd_iterative(num1, num2);
    std::cout << "UCLN(" << num1 << ", " << num2 << ") (De quy) = " << result_recursive << std::endl; // Ket qua: 6
    std::cout << "UCLN(" << num1 << ", " << num2 << ") (Lap) = " << result_iterative << std::endl; // Ket qua: 6


    return 0;
}

Giải thích code ví dụ:

• Chúng ta khai báo các biến num1 và num2 để lưu cặp số cần tính ƯCLN.
• Gọi cả hai hàm gcd_recursive và gcd_iterative với cùng cặp số để chứng minh rằng chúng cho kết quả giống nhau.
• Sử dụng std::cout để in kết quả ra màn hình console.
• Thêm các ví dụ với các cặp số khác nhau (số nguyên tố cùng nhau, số lớn hơn/nhỏ hơn nhiều, số âm) để kiểm tra tính đúng đắn của hàm.
• Lưu ý: Trong code ví dụ này, tôi đã thêm std::abs() vào đầu mỗi hàm gcd để xử lý trường hợp số âm một cách đơn giản. Nếu chỉ làm việc với số dương, bạn có thể bỏ std::abs().

Từ C++17 trở đi, thư viện <numeric> đã cung cấp sẵn hàm std::gcd cho bạn sử dụng, hàm này thường được tối ưu hóa tốt nhất. Tuy nhiên, việc hiểu và tự triển khai thuật toán Euclid là rất quan trọng cho việc học CTDL&GT.

3. Bội số chung nhỏ nhất (BCNN) - LCM

Bội số chung nhỏ nhất (BCNN) của hai hoặc nhiều số nguyên dương là số nguyên dương nhỏ nhất khác 0 mà là bội của tất cả các số đó. Trong tiếng Anh, nó được gọi là Least Common Multiple (LCM).

Ví dụ:

• Bội của 12 là: 12, 24, 36, 48, 60, 72, ...
• Bội của 18 là: 18, 36, 54, 72, 90, ...
• Các bội chung của 12 và 18 là: 36, 72, ...
• Bội số chung nhỏ nhất của 12 và 18 là: 36. Ký hiệu: BCNN(12, 18) = 36 hoặc lcm(12, 18) = 36.

Mối liên hệ kỳ diệu giữa ƯCLN và BCNN

Có một mối liên hệ đẹp đẽ giữa ƯCLN và BCNN của hai số nguyên dương a và b:

ƯCLN(a, b) * BCNN(a, b) = a * b

Từ đó, chúng ta có thể dễ dàng tính BCNN nếu đã có ƯCLN:

BCNN(a, b) = (a * b) / ƯCLN(a, b)

Công thức này cho phép chúng ta sử dụng thuật toán Euclid hiệu quả để tính BCNN mà không cần phải liệt kê bội số.

Lưu ý: Nếu a hoặc b bằng 0, thì BCNN của chúng là 0. Công thức trên cần được xem xét cẩn thận nếu cho phép số 0. Với a, b dương, công thức này hoàn toàn đúng. Khi làm việc với số âm, chúng ta thường tính BCNN của giá trị tuyệt đối của chúng.

Triển khai BCNN bằng C++

Sử dụng công thức trên và hàm tính ƯCLN đã có.

#include <iostream> // Cần cho std::cout, std::endl
#include <cmath>    // Cần cho std::abs

// Bao gồm một trong hai hàm gcd đã viết ở trên, ví dụ dùng bản lặp
int gcd_iterative(int a, int b) {
    a = std::abs(a);
    b = std::abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// Hàm tính BCNN sử dụng ƯCLN
long long lcm(long long a, long long b) { // Sử dụng long long để tránh tràn số khi nhân a * b
    if (a == 0 || b == 0) {
        return 0; // BCNN của 0 và bất kỳ số nào khác là 0
    }
    // Tính BCNN sử dụng công thức: lcm(a, b) = (|a*b|) / gcd(|a|, |b|)
    // Cách tính sau an toàn hơn tránh tràn số khi a*b quá lớn:
    // lcm(a, b) = (|a| / gcd(|a|, |b|)) * |b|
    long long common_divisor = gcd_iterative(std::abs(a), std::abs(b));
    return (std::abs(a) / common_divisor) * std::abs(b);
}

Giải thích code:

• Hàm lcm nhận hai số nguyên a và b. Tôi sử dụng long long cho các tham số và giá trị trả về để có thể xử lý các kết quả BCNN lớn hơn phạm vi của int thông thường (khi a*b lớn).
• if (a == 0 || b == 0) xử lý trường hợp đặc biệt khi một trong hai số là 0.
• long long common_divisor = gcd_iterative(std::abs(a), std::abs(b)); tính ƯCLN của giá trị tuyệt đối của a và b bằng hàm gcd_iterative (hoặc gcd_recursive đều được).
• return (std::abs(a) / common_divisor) * std::abs(b); là việc áp dụng công thức BCNN. Chia |a| cho ƯCLN trước rồi mới nhân với |b| giúp giữ các giá trị trung gian nhỏ hơn, giảm nguy cơ tràn số so với việc nhân |a| * |b| trước rồi mới chia.

Ví dụ minh họa C++ cho BCNN

Sử dụng hàm lcm vừa viết.

#include <iostream> // Cần cho std::cout, std::endl
#include <cmath>    // Cần cho std::abs

// Bao gồm hàm gcd_iterative (hoặc gcd_recursive) và hàm lcm đã viết ở trên

int gcd_iterative(int a, int b) {
    a = std::abs(a);
    b = std::abs(b);
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) {
        return 0;
    }
    long long common_divisor = gcd_iterative(std::abs(a), std::abs(b));
    return (std::abs(a) / common_divisor) * std::abs(b);
}


int main() {
    long long num1 = 12;
    long long num2 = 18;

    std::cout << "--- Minh hoa tinh Toan BCNN ---" << std::endl;

    // Su dung ham lcm
    long long result_lcm = lcm(num1, num2);
    std::cout << "BCNN(" << num1 << ", " << num2 << ") = " << result_lcm << std::endl; // Ket qua: 36

    std::cout << std::endl; // Xuong dong

    // Thu voi cap so khac
    num1 = 10;
    num2 = 15;
    result_lcm = lcm(num1, num2);
    std::cout << "BCNN(" << num1 << ", " << num2 << ") = " << result_lcm << std::endl; // Ket qua: 30

     std::cout << std::endl; // Xuong dong

    // Thu voi so nguyen to cung nhau
    num1 = 7;
    num2 = 9;
    result_lcm = lcm(num1, num2);
    std::cout << "BCNN(" << num1 << ", " << num2 << ") = " << result_lcm << std::endl; // Ket qua: 63 (7*9 vi UCLN(7,9)=1)

     std::cout << std::endl; // Xuong dong

     // Thu voi so 0
    num1 = 0;
    num2 = 100;
    result_lcm = lcm(num1, num2);
    std::cout << "BCNN(" << num1 << ", " << num2 << ") = " << result_lcm << std::endl; // Ket qua: 0

    return 0;
}

Giải thích code ví dụ:

• Khai báo các biến num1 và num2 kiểu long long.
• Gọi hàm lcm với các cặp số khác nhau.
• In kết quả ra màn hình. Các ví dụ minh họa cách tính BCNN cho các trường hợp khác nhau, bao gồm cả số nguyên tố cùng nhau (có ƯCLN là 1, BCNN bằng tích của chúng) và trường hợp số 0.

4. Các ứng dụng của ƯCLN và BCNN

ƯCLN và BCNN không chỉ là các khái niệm toán học trên giấy. Chúng có nhiều ứng dụng thực tế trong lập trình:

• Đơn giản hóa phân số: Để rút gọn phân số a/b, ta chia cả tử và mẫu cho ƯCLN(a, b).
• Tìm mẫu số chung nhỏ nhất: Khi cộng hoặc trừ các phân số, BCNN của các mẫu số chính là mẫu số chung nhỏ nhất.
• Các bài toán về chu kỳ: Tìm thời điểm hai hay nhiều sự kiện lặp lại cùng xảy ra lần tiếp theo thường liên quan đến BCNN.
• Trong đồ họa: Thuật toán Bresenham's line algorithm (vẽ đường thẳng trên màn hình pixel) sử dụng khái niệm tương tự như thuật toán Euclid.
• Mật mã học: Các khái niệm về ƯCLN, đặc biệt là thuật toán Euclid mở rộng (extended Euclidean algorithm), là nền tảng cho nhiều thuật toán mật mã hiện đại như thuật toán RSA.

Bài tập ví dụ:

Chia hết hay không?

Trong một buổi triển lãm nghệ thuật, FullHouse Dev được thử thách với một bài toán thú vị về số học. Họ phải xem xét mối quan hệ giữa tích và tổng của một chuỗi số, như thể đang phân tích nhịp điệu của một bản nhạc hoàn hảo.

Bài toán

Cho một hoán vị các số từ \(1\) đến \(n\). Gọi \(P\) là tích của tất cả các phần tử trong hoán vị và \(S\) là tổng của chúng. Với một số nguyên dương \(n\) cho trước, nhiệm vụ của bạn là xác định xem \(P\) có chia hết cho \(S\) hay không.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Mỗi test case chứa một số nguyên \(n\) - độ dài của hoán vị

OUTPUT FORMAT:

• Với mỗi test case, in ra "YES" nếu \(P\) chia hết cho \(S\), ngược lại in ra "NO"

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq n \leq 10^5\)

Ví dụ

INPUT

2
2
3

OUTPUT

NO
YES

Giải thích

• Ở test case đầu tiên, với \(n = 2\), \(P\) không chia hết cho \(S\)
• Ở test case thứ hai, với \(n = 3\), \(P\) chia hết cho \(S\) Đây là hướng dẫn giải bài "Chia hết hay không?" bằng C++ một cách ngắn gọn:

1. Hiểu rõ Bài toán:

   • Bạn được cho một số nguyên dương n.
   • P là tích của các số từ 1 đến n, tức là n!.
   • S là tổng của các số từ 1 đến n, tức là 1 + 2 + ... + n = n * (n + 1) / 2.
   • Bài toán yêu cầu kiểm tra xem P có chia hết cho S hay không. Lưu ý rằng "hoán vị" chỉ là cách nói, tích và tổng của các số từ 1 đến n luôn cố định bất kể thứ tự.

2. Thiết lập điều kiện chia hết:

   • Cần kiểm tra xem n! có chia hết cho n * (n + 1) / 2 không.
   • Điều này tương đương với việc kiểm tra xem n! chia (n * (n + 1) / 2) có ra số nguyên hay không.
   • Biến đổi biểu thức: n! / (n * (n + 1) / 2) = (1 * 2 * ... * (n-1) * n) / (n * (n + 1) / 2)
   • Triệt tiêu n (với n >= 1): = (1 * 2 * ... * (n-1)) / ((n + 1) / 2)
   • = (n-1)! / ((n + 1) / 2) = 2 * (n-1)! / (n + 1)
   • Vậy, bài toán quy về kiểm tra xem 2 * (n-1)! có chia hết cho n + 1 hay không.

3. Phân tích điều kiện 2 * (n-1)! chia hết cho n + 1:

   • Xét n = 1: n+1 = 2, 2 * (1-1)! = 2 * 0! = 2 * 1 = 2. 2 chia hết cho 2. Kết quả YES.
   • Xét n > 1:
     • Nếu n + 1 là số nguyên tố p > 2: p không chia hết cho 2 và p không thể là thừa số trong (n-1)! vì tất cả các thừa số trong (n-1)! đều nhỏ hơn p = n+1. Do đó, p không chia hết 2 * (n-1)!. Kết quả NO.
     • Nếu n + 1 là hợp số: Mọi thừa số nguyên tố p của n+1 đều nhỏ hơn hoặc bằng (n+1)/2. Đối với n >= 3, (n+1)/2 <= n-1. Do đó, mọi thừa số nguyên tố của n+1 đều xuất hiện trong tích (n-1)!. Bạn cần chứng minh rằng lũy thừa của mỗi thừa số nguyên tố trong n+1 không vượt quá lũy thừa tương ứng trong 2 * (n-1)!. Điều này luôn đúng khi n+1 là hợp số (trừ trường hợp đặc biệt n+1=4 hay n=3, nơi n+1 là 2^2 và n-1=2, 2*2! = 4 vẫn chia hết cho 4). Nói chung, nếu n+1 là hợp số (và n > 1), thì n+1 chia hết 2 * (n-1)!. Kết quả YES.

4. Công thức rút gọn:

   • Từ phân tích trên, kết quả là YES nếu n = 1 hoặc n + 1 là hợp số.
   • Kết quả là NO nếu n > 1 và n + 1 là số nguyên tố.
   • Điều này có thể viết gọn lại là: Trả về YES nếu n == 1 hoặc n + 1 KHÔNG phải là số nguyên tố. Trả về NO nếu n > 1 và n + 1 là số nguyên tố.

5. Thuật toán:

   • Đọc số lượng test case T.
   • Lặp lại T lần:
     • Đọc số nguyên n.
     • Nếu n == 1, in ra "YES".
     • Nếu n > 1, cần kiểm tra xem n + 1 có phải số nguyên tố hay không:
       • Viết một hàm kiểm tra số nguyên tố isPrime(k):
         • Nếu k <= 1, trả về false.
         • Nếu k == 2, trả về true.
         • Nếu k % 2 == 0, trả về false.
         • Duyệt qua các số lẻ i từ 3 đến sqrt(k). Nếu k % i == 0, trả về false.
         • Nếu vòng lặp kết thúc mà không tìm thấy ước, trả về true.
       • Gọi hàm isPrime(n + 1).
       • Nếu isPrime(n + 1) trả về true, in ra "NO".
       • Nếu isPrime(n + 1) trả về false, in ra "YES".

6. Lưu ý cài đặt:

   • Sử dụng kiểu dữ liệu long long cho n nếu cần thiết (nhưng ràng buộc n <= 10^5 cho thấy int là đủ cho n và n+1, phép tính sqrt cũng trong giới hạn).
   • Hàm isPrime cần tính sqrt (hoặc kiểm tra i * i <= k để tránh dùng số thực).ơ

Làm thêm nhiều bài tập miễn phí tại đây