Bài 10.5: Bài tập thực hành lý thuyết số với hàm trong C++

Chào mừng các bạn quay trở lại với hành trình khám phá C++ cùng FullhouseDev! Trong các bài viết trước, chúng ta đã tìm hiểu về những kiến thức cơ bản và cấu trúc điều khiển. Hôm nay, chúng ta sẽ đi sâu vào một lĩnh vực vừa cổ điển vừa hiện đại: lý thuyết số, và quan trọng hơn, cách chúng ta áp dụng công cụ mạnh mẽ là hàm (functions) trong C++ để giải quyết các bài toán thuộc lĩnh vực này một cách hiệu quả và có tổ chức.

Lý thuyết số là một nhánh của toán học nghiên cứu về các số nguyên và tính chất của chúng. Tuy nghe có vẻ hàn lâm, nhưng lý thuyết số lại có vô số ứng dụng thực tế trong khoa học máy tính, từ mật mã học (cryptography), thuật toán (algorithms), cho đến những vấn đề tối ưu hóa.

Khi giải quyết các bài toán lý thuyết số trong lập trình, chúng ta thường gặp phải những thao tác lặp đi lặp lại, ví dụ như kiểm tra một số có phải số nguyên tố không, hay tìm ước chung lớn nhất của hai số. Đây chính là lúc hàm phát huy vai trò của mình! Bằng cách đóng gói các logic xử lý cụ thể vào các hàm riêng biệt, chúng ta không chỉ làm cho code của mình dễ đọc, dễ bảo trì mà còn có thể tái sử dụng chúng ở nhiều nơi khác nhau trong cùng một chương trình hoặc thậm chí là các chương trình khác.

Hãy cùng đi qua một số bài toán lý thuyết số cơ bản và xem cách chúng ta xây dựng các hàm C++ để giải quyết chúng nhé!

Kiểm tra số nguyên tố (Primality Test)

Bài toán kinh điển nhất trong lý thuyết số là kiểm tra xem một số nguyên dương có phải là số nguyên tố hay không. Một số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước dương phân biệt là 1 và chính nó.

Để kiểm tra một số n có phải số nguyên tố không, chúng ta chỉ cần kiểm tra xem nó có chia hết cho bất kỳ số nào từ 2 đến căn bậc hai của n hay không. Nếu có, nó không phải số nguyên tố. Nếu không, nó là số nguyên tố.

Dưới đây là hàm C++ thực hiện kiểm tra này:

#include <iostream>
#include <cmath> // Cần thư viện cmath để sử dụng sqrt

// Hàm kiểm tra xem một số có phải là số nguyên tố không
bool isPrime(int n) {
    // Số nhỏ hơn hoặc bằng 1 không phải số nguyên tố
    if (n <= 1) {
        return false;
    }
    // Chỉ cần kiểm tra tính chia hết đến căn bậc hai của n
    // Sử dụng i * i <= n thay vì i <= sqrt(n) để tránh làm việc với số thực
    for (int i = 2; i * i <= n; ++i) {
        // Nếu n chia hết cho i, thì n không phải số nguyên tố
        if (n % i == 0) {
            return false;
        }
    }
    // Nếu không tìm thấy ước nào trong phạm vi kiểm tra, n là số nguyên tố
    return true;
}

int main() {
    int num1 = 17; // Một số nguyên tố
    int num2 = 4;  // Không phải số nguyên tố

    // Gọi hàm isPrime và in kết quả
    if (isPrime(num1)) {
        cout << num1 << " là số nguyên tố." << endl; // Output: 17 là số nguyên tố.
    } else {
        cout << num1 << " không phải là số nguyên tố." << endl;
    }

    if (isPrime(num2)) {
        cout << num2 << " là số nguyên tố." << endl;
    } else {
        cout << num2 << " không phải là số nguyên tố." << endl; // Output: 4 không phải là số nguyên tố.
    }

    return 0;
}

Giải thích code:

Hàm isPrime nhận vào một số nguyên n và trả về true nếu n là số nguyên tố, ngược lại trả về false.
Chúng ta xử lý trường hợp n <= 1 ngay đầu vì chúng không phải số nguyên tố theo định nghĩa.
Vòng lặp for bắt đầu từ i = 2. Điều kiện lặp i * i <= n tương đương với i <= sqrt(n) nhưng tránh sử dụng số thực, giúp tăng độ chính xác và hiệu quả một chút.
Bên trong vòng lặp, nếu n % i == 0, nghĩa là n chia hết cho i (một số khác 1 và nhỏ hơn hoặc bằng căn bậc hai của n), thì n không phải số nguyên tố, chúng ta trả về false ngay lập tức.
Nếu vòng lặp kết thúc mà không tìm thấy ước nào, điều đó có nghĩa n chỉ chia hết cho 1 và chính nó (đối với n > 1), nên nó là số nguyên tố, chúng ta trả về true.
Hàm main minh họa cách gọi hàm isPrime với hai số khác nhau và in ra kết quả.

Tìm ước chung lớn nhất (GCD - Greatest Common Divisor)

Ước chung lớn nhất (GCD) của hai số nguyên a và b là số nguyên dương lớn nhất chia hết cho cả a và b mà không dư. Ví dụ, GCD của 48 và 18 là 6.

Để tìm GCD, chúng ta có thể sử dụng thuật toán Euclidean, một trong những thuật toán lâu đời và hiệu quả nhất. Thuật toán này dựa trên nguyên lý: GCD của hai số a và b (với a > b) bằng GCD của b và phần dư của a khi chia cho b (a % b). Quá trình này lặp lại cho đến khi phần dư bằng 0; khi đó, số còn lại chính là GCD.

Đây là hàm C++ dựa trên thuật toán Euclidean (phiên bản lặp):

#include <iostream>
#include <cmath> // Cần cho abs để xử lý số âm nếu có

// Hàm tìm ước chung lớn nhất sử dụng thuật toán Euclidean
int findGCD(int a, int b) {
    // Đảm bảo chúng ta làm việc với các giá trị không âm
    a = abs(a);
    b = abs(b);

    // Thuật toán Euclidean
    while (b != 0) {
        int temp = b;
        b = a % b; // Tính phần dư mới
        a = temp;  // Cập nhật a thành giá trị của b trước đó
    }
    // Khi b bằng 0, giá trị của a chính là GCD
    return a;
}

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

    // Gọi hàm findGCD và in kết quả
    int gcd = findGCD(num1, num2);
    cout << "Ước chung lớn nhất của " << num1 << " và " << num2 << " là: " << gcd << endl; // Output: Ước chung lớn nhất của 48 và 18 là: 6

    return 0;
}

Giải thích code:

Hàm findGCD nhận hai số nguyên a và b. Chúng ta sử dụng abs để đảm bảo tính toán với giá trị tuyệt đối, giúp xử lý đúng cả khi số nhập vào là âm.
Vòng lặp while (b != 0) tiếp tục cho đến khi số thứ hai (ban đầu là b, sau mỗi lần lặp là phần dư) bằng 0.
Bên trong vòng lặp:
- int temp = b; lưu trữ giá trị hiện tại của b.
- b = a % b; tính phần dư của a chia cho b và gán cho b mới.
- a = temp; gán giá trị b cũ (đã lưu trong temp) cho a mới.
Khi vòng lặp dừng lại (do b bằng 0), giá trị cuối cùng của a chính là GCD của hai số ban đầu.
Hàm main minh họa cách gọi hàm findGCD và in kết quả.

Tìm bội chung nhỏ nhất (LCM - Least Common Multiple)

Bội chung nhỏ nhất (LCM) của hai số nguyên a và b là số nguyên dương nhỏ nhất chia hết cho cả a và b. Ví dụ, LCM của 12 và 18 là 36.

LCM có mối liên hệ chặt chẽ với GCD qua công thức sau: lcm(a, b) = (|a * b|) / gcd(a, b)

Chúng ta có thể sử dụng lại hàm findGCD đã xây dựng để tính LCM.

Dưới đây là hàm C++ tìm LCM:

#include <iostream>
#include <cmath> // Cần cho abs

// Giả sử hàm findGCD đã được định nghĩa ở trên hoặc trong một header file khác.
// Để code ví dụ này hoạt động độc lập, ta định nghĩa lại hàm findGCD ở đây:
int findGCD(int a, int b) {
     a = abs(a);
     b = abs(b);
     while (b != 0) {
         int temp = b;
         b = a % b;
         a = temp;
     }
     return a;
}

// Hàm tìm bội chung nhỏ nhất sử dụng công thức LCM = (|a*b|) / GCD(a,b)
long long findLCM(int a, int b) {
    // Bội chung nhỏ nhất của 0 với bất kỳ số nào là 0
    if (a == 0 || b == 0) {
        return 0;
    }
    // Sử dụng long long cho kết quả để tránh tràn số, vì a * b có thể rất lớn.
    // Cách tính (long long)abs(a) / findGCD(a, b) * abs(b)
    // giúp tránh tràn số trung gian khi nhân a*b trước khi chia.
    return (long long)abs(a) / findGCD(a, b) * abs(b);
}

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

    // Gọi hàm findLCM và in kết quả
    long long lcm = findLCM(num1, num2);
    cout << "Bội chung nhỏ nhất của " << num1 << " và " << num2 << " là: " << lcm << endl; // Output: Bội chung nhỏ nhất của 12 và 18 là: 36

    return 0;
}

Giải thích code:

Hàm findLCM nhận hai số nguyên a và b.
Chúng ta xử lý trường hợp a == 0 hoặc b == 0 vì LCM trong trường hợp này là 0.
Để tính LCM, chúng ta sử dụng công thức (|a * b|) / gcd(a, b).
Một điểm quan trọng cần lưu ý là tích a * b có thể vượt quá giới hạn của kiểu int nếu a và b đủ lớn. Do đó, chúng ta sử dụng kiểu long long cho giá trị trả về của hàm findLCM và khi thực hiện phép tính.
Cách tính (long long)abs(a) / findGCD(a, b) * abs(b) được ưu tiên hơn là (long long)abs(a) * abs(b) / findGCD(a, b) để giảm thiểu nguy cơ tràn số trung gian. Bằng cách chia abs(a) cho GCD trước rồi mới nhân với abs(b), chúng ta làm việc với các số có giá trị trung gian nhỏ hơn.
Hàm main minh họa cách gọi hàm findLCM và in kết quả.

Phân tích thừa số nguyên tố (Prime Factorization)

Phân tích thừa số nguyên tố là quá trình biểu diễn một số nguyên dương lớn hơn 1 dưới dạng tích của các số nguyên tố. Ví dụ: 12 = 2 * 2 * 3, 30 = 2 * 3 * 5, 72 = 2 * 2 * 2 * 3 * 3.

Để phân tích một số n thành thừa số nguyên tố, chúng ta có thể áp dụng thuật toán đơn giản sau:

Chia n cho 2 liên tục cho đến khi nó không chia hết cho 2 nữa. In ra số 2 mỗi lần chia.
Sau khi xử lý số 2, n trở thành một số lẻ. Bắt đầu kiểm tra các số lẻ từ 3 trở lên.
Với mỗi số lẻ i (bắt đầu từ 3, tăng dần 2 đơn vị), chia n cho i liên tục cho đến khi nó không chia hết cho i nữa. In ra i mỗi lần chia. Chỉ cần kiểm tra các số i cho đến khi i * i > n.
Nếu sau khi vòng lặp kết thúc mà n vẫn còn lớn hơn 1, điều đó có nghĩa là n hiện tại là một số nguyên tố (và là thừa số nguyên tố lớn nhất), in ra giá trị của n.

Đây là hàm C++ thực hiện phân tích thừa số nguyên tố:

#include <iostream>
#include <cmath> // Cần cho sqrt (mặc dù ta dùng i*i <= n)

// Hàm phân tích một số ra thừa số nguyên tố và in ra kết quả
void primeFactorization(int n) {
    // Xử lý các trường hợp đặc biệt 0 và 1
    if (n <= 1) {
        cout << n << endl;
        return;
    }

    // Xử lý thừa số 2: Chia n cho 2 cho đến khi không chia hết nữa
    while (n % 2 == 0) {
        cout << 2 << " ";
        n /= 2;
    }

    // Xử lý các thừa số lẻ: Bắt đầu từ 3, tăng 2 đơn vị (chỉ kiểm tra số lẻ)
    // Chỉ cần kiểm tra đến căn bậc hai của n hiện tại
    for (int i = 3; i * i <= n; i = i + 2) {
        // Chia n cho i cho đến khi không chia hết nữa
        while (n % i == 0) {
            cout << i << " ";
            n /= i;
        }
    }

    // Nếu sau các bước trên n vẫn còn lớn hơn 1,
    // thì n chính là một số nguyên tố lớn (thừa số nguyên tố cuối cùng)
    if (n > 1) {
        cout << n << " ";
    }
    cout << endl; // Xuống dòng sau khi in xong các thừa số
}

int main() {
    int num1 = 72; // 2 * 2 * 2 * 3 * 3
    cout << "Phân tích " << num1 << " thành thừa số nguyên tố: ";
    primeFactorization(num1);

    int num2 = 29; // Là số nguyên tố
    cout << "Phân tích " << num2 << " thành thừa số nguyên tố: ";
    primeFactorization(num2);

    int num3 = 1;
    cout << "Phân tích " << num3 << " thành thừa số nguyên tố: ";
    primeFactorization(num3);

    return 0;
}

Giải thích code:

Hàm primeFactorization nhận một số nguyên dương n. Hàm này sử dụng void vì nó chỉ thực hiện việc in ra các thừa số, không trả về một giá trị cụ thể.
Trường hợp n <= 1 được xử lý riêng.
Vòng lặp while (n % 2 == 0) xử lý tất cả các thừa số 2.
Vòng lặp for sau đó xử lý các thừa số lẻ. Nó bắt đầu từ i = 3 và chỉ kiểm tra các số lẻ (i = i + 2). Điều kiện lặp i * i <= n giúp tối ưu hóa, vì nếu n có một thừa số nguyên tố lớn hơn căn bậc hai của nó, thì thừa số đó phải là chính n sau khi đã chia hết cho các thừa số nhỏ hơn.
Vòng lặp while (n % i == 0) bên trong vòng lặp for đảm bảo rằng chúng ta in ra và chia n cho cùng một thừa số i nhiều lần nếu nó xuất hiện lặp lại trong phân tích.
Sau cùng, nếu n còn lại lớn hơn 1, nó chắc chắn là một số nguyên tố và là thừa số cuối cùng cần in ra.
Hàm main minh họa cách gọi hàm primeFactorization với các số khác nhau.

Comments

There are no comments at the moment.