Bài 23. Phân tích thừa số nguyên tố trong C/C++

Giới thiệu

Bài toán phân tích thừa số nguyên tố là một bài tập lập trình cơ bản thường được sử dụng trong các bài thi nhập môn lập trình. Trong bài chia sẻ này, chúng ta sẽ cùng tìm hiểu và giải quyết bài toán phân tích thừa số nguyên tố này.

1. Đề bài phân tích thừa số nguyên tố

Bài toán yêu cầu chúng ta phân tích một số tự nhiên N thành tích các thừa số nguyên tố. Chúng ta cần nhập vào một số nguyên dương N và tìm các thừa số nguyên tố của N.

Ví dụ:

• 8 = 2^3
• 100 = 2^2 * 5^2
• 999 = 3^3 * 37

2. Ý tưởng giải bài toán phân tích thừa số nguyên tố

Ý tưởng giải bài toán rất đơn giản. Chúng ta chỉ cần chia số N cho các số nguyên tố từ 2 đến N. Với mỗi số nguyên tố đó, ta đếm số lần mà số N chia hết. Sau mỗi lần chia cho số nguyên tố đó, ta giảm số N đi lần chia.

Ví dụ: Giả sử N = 300: 300 / 2 = 150 150 / 2 = 75 75 / 3 = 25 25 / 5 = 5 5 / 5 = 1

Khi đó, 300 = 2^2 3 5.

Đối với các số chia lớn hơn số N, chúng ta sẽ dừng quá trình chia.

3. Mã nguồn phân tích thừa số nguyên tố

Dưới đây là mã nguồn phân tích thừa số nguyên tố bằng ngôn ngữ C:

#include 

int main(){
    int n;
    printf("Nhập n = ");
    scanf("%d", &n);

    int dem;
    for(int i = 2; i <= n; i++){
        dem = 0;
        while(n % i == 0){
            ++dem;
            n /= i;
        }
        if(dem){
            if(dem > 1) printf("%d^%d", i, dem);
            else printf("%d", i);
            if(n > i){
                printf(" * ");
            }
        }
    }
}

Với ngôn ngữ C++, mã nguồn sẽ như sau:

#include 
using namespace std;

int main(){
    int n;
    cout << "Nhập n = ";
    cin >> n;

    int dem;
    for(int i = 2; i <= n; i++){
        dem = 0;
        while(n % i == 0){
            ++dem;
            n /= i;
        }
        if(dem){
            cout << i;
            if(dem > 1) cout << "^" << dem;
            if(n > i){
                cout << " * ";
            }
        }
    }
}

Kết luận

Phân tích thừa số nguyên tố là một bài toán lập trình cơ bản. Chúng ta đã tìm hiểu ý tưởng giải bài toán và mã nguồn cụ thể cho các ngôn ngữ C và C++. Hy vọng bài chia sẻ này đã giúp bạn hiểu rõ hơn về cách phân tích thừa số nguyên tố.