Tìm tất cả các ước số của một số nguyên trong C++

Trong toán học, ước số được định nghĩa như sau:

Ước số của một số tự nhiên A là B khi A chia hết cho B.

Ví dụ, số 6 có các ước số là 1, 2, 3 và 6. Vì 6 chia hết cho cả 1, 2, 3 và 6. Lưu ý: Trong bài này, khi nói về ước số, chúng ta chỉ xét các số nguyên dương.

1. Sử dụng vòng lặp và toán tử chia lấy dư

Để tìm tất cả các ước số của một số nguyên dương trong C++, ta có thể sử dụng một vòng lặp để kiểm tra tất cả các số từ 1 đến số nguyên đó. Nếu số nguyên dương đó chia hết cho số nào thì số đó là ước số. Dưới đây là một đoạn code minh họa:

#include <iostream>
using namespace std;

int main()
{
    int num;
    cout << "Nhap vao mot so nguyen: ";
    cin >> num;
    cout << "Cac uoc so cua " << num << " la: ";
    for (int i = 1; i <= num; i++) {
        if (num % i == 0) {
            cout << i << " ";
        }
    }
    return 0;
}

Trong đoạn code trên, chúng ta sử dụng vòng lặp for để duyệt qua tất cả các số từ 1 đến num. Với mỗi số i, chúng ta kiểm tra xem num có chia hết cho i hay không bằng cách sử dụng toán tử chia lấy dư (%). Nếu num chia hết cho i, thì i là một ước số của num và chúng ta in giá trị đó ra màn hình.

Lưu ý: Muốn kiểm tra người dùng nhập số nguyên dương hợp lệ hay không thì các bạn xem lại bài đếm số chữ số của một số nguyên dương trong C++.

2. Cách tối ưu để tìm ước số của một số nguyên trong C++

Khi để ý kỹ, chúng ta sẽ thấy tất cả các ước số của một số nguyên đều đi theo một cặp. Ví dụ: số nguyên num = 100 có các cặp ước số là (1,100), (2,50), (4,25), (5,20), (10,10). Nếu để ý kỹ thì ta sẽ thấy một số nguyên dương >= 2 bất kỳ sẽ luôn có số ước số ở nửa đầu căn bậc 2 của nó bằng số ước ở nửa sau căn bậc 2 của nó. Các ước số sẽ phân bố thành 2 miền từ [2; sqrt(num)] và từ [sqrt(num); num].

Chương trình bên dưới là cách tối ưu để tìm tất cả các ước số của một số nguyên dương trong C++:

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int num;
    cout << "Nhap vao mot so nguyen: ";
    cin >> num;
    cout << "Cac uoc so cua " << num << " la: ";
    for (int i = 1; i <= sqrt(num); i++) {
        if (num % i == 0) {
            //Neu num chia i bang i thi chi in ra i
            if (num/i == i){
                cout <<" "<< i;
            }else {//Nguoc lai, in ra i va num/i
                cout << " "<< i << " " << num/i;
            }
        }
    }
    return 0;
}

Kết quả

Nhap vao mot so nguyen: 100
Cac uoc so cua 100 la:  1 100 2 50 4 25 5 20 10

Các ước số được tìm ra một cách chính xác và nhanh chóng hơn khi phải duyệt từ 1 đến num. Nhưng có một vấn đề là các ước số được in ra theo từng cặp chứ không theo thứ tự. Các bạn có thể viết đoạn code để sắp xếp các ước số theo thứ tự tăng dần.