Phân tích thừa số nguyên tố trong C/C++

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 thường được sử dụng trong các bài thi nhập môn lập trình. Trong bài 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 nhập vào số nguyên dương N, và phân tích số N thành tích các thừa số nguyên tố.

Ví dụ:

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

2. Ý tưởng giải bài toán

Để giải bài toán này, chúng ta chỉ cần thực hiệ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à N chia hết. Sau mỗi lần chia, giá trị của N sẽ giảm đi số lần chia hết.

Ví dụ:

Với N = 300, ta có quá trình như sau: 300 ÷ 2 = 150 ÷ 2 = 75 ÷ 5 = 15 ÷ 5 = 3 ÷ 3 = 1. Khi đó, ta có 300 = 2^2 3 5^2.
Với N = 999, khi N chỉ còn 37, mà 37 là số nguyên tố, nên ta dừng quá trình chia. Khi đó, ta có 999 = 3^3 * 37.

Quy tắc chung là chúng ta sẽ dừng quá trình chia khi số chia lớn hơn N.

3. Code phân tích thừa số nguyên tố

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

#include <stdio.h>
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 ý tưởng tương tự, chúng ta có thể sử dụng ngôn ngữ C++ để viết code như sau:

#include <iostream>
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 << " * ";
            }
        }
    }
}

Khi chạy code, chúng ta sẽ có kết quả như sau:

Nhập n = 126
2 * 3^2 * 7

Đối với số N lớn, chúng ta có thể sử dụng cấu trúc map trong ngôn ngữ C++. Dưới đây là code tối ưu hơn sử dụng map:

#include <iostream>
#include <map>
using namespace std;
int main(){
    int N;
    cout << "Nhập n = ";
    cin >> N;

    map<int, int> m;
    for(int i = 2; i <= N; i++){
        while(N % i == 0){
            m[i]++;
            N /= i;
        }
    }

    for(auto it : m){
        cout << it.first << " " << it.second << endl;
    }
}

Lưu ý: Lời giải này sử dụng biến auto, chỉ có trong C++ 11 trở lên. Để chạy được, cần thêm flag: std=c++11.

Hy vọng qua bài viết này, bạn đã hiểu và giải quyết bài toán phân tích thừa số nguyên tố. Nếu bạn cần thêm thông tin, hãy để lại bình luận, tôi sẽ giúp bạn nhé.